定义了点,向量的结构体,重载运算符
二分判断即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct oppo{
int x,y;
oppo(){};
oppo(int x,int y):x(x),y(y){};
oppo operator -(){
return oppo(-x,-y);
}
oppo operator -(oppo b){
return oppo(x-b.x,y-b.y);
}
oppo operator +(oppo b){
return oppo(x+b.x,y+b.y);
}
oppo operator *(int b){
return oppo(x*b,y*b);
}
int operator *(oppo b){
return x*b.x+y*b.y;//点乘
}
int operator ^(oppo b){
return x*b.y-y*b.x;//叉乘
}
oppo operator /(int b){
return oppo(x/b,y/b);
}
void out(){
printf("(%lld,%lld)\n",x,y);
}
}p[10000][3];
int tot[10000];
int n,m,x,y,xx,yy;
void find(oppo k)
{
int l=1,r=n,mid,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(((k-p[mid][0])^(p[mid][1]-p[mid][0]))>=0){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
tot[ans]++;
}
int T;
signed main()
{
while(++T)
{
scanf("%lld",&n);if(!n) break;
if(T!=1) puts("");
scanf("%lld%lld%lld%lld%lld",&m,&x,&y,&xx,&yy);
memset(tot,0,sizeof(tot));
for(int i=1;i<=n;i++){
int a,b;
scanf("%lld%lld",&a,&b);
p[i][1]=oppo(a,y);
p[i][0]=oppo(b,yy);
}
for(int i=1;i<=m;i++){
int a,b;
scanf("%lld%lld",&a,&b);
find(oppo(a,b));
}
for(int i=0;i<=n;i++)
printf("%lld: %lld\n",i,tot[i]);
}
return 0;
}