题目链接https://cn.vjudge.net/problem/POJ-2318；
利用叉积，判断距离点最近的直线，二分搜索优化一下；
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include<math.h> using namespace std; #define ll long long double cutmid; const double esp=0.000000001; const long long int INF=0x3f3f3f3f3f3f3f3f; //const double PI=acos(-1); int T,n,m; int arr[5050]; int dw[5050]; struct node { int x,y; node(){} node(ll a,ll b){x=a,y=b;} node operator - (const node &a)const { return node(x-a.x,y-a.y); } double operator ^ (const node &a)const{ return x*a.x+y*a.y; } double operator * (const node &a)const{ return x*a.y-y*a.x; } bool operator < (const node &t)const{ /// 极角排序 bool up[2]={0,0}; if(y>0 || (y==0 && x>0)) up[0]=1; if(t.y>0 || (t.y==0 && t.x>0)) up[1]=1; if(up[0]^up[1]) return up[0]; return (*this)*t ? (*this)*t>0 : ((*this)^(*this))<(t^t); } }p[5050]; struct Line { node s,e; Line(){} Line(node s1,node e1) { s=s1,e=e1; } }wall[5050]; int cmp(Line a,Line b) { return a.s.x<b.s.x; } long long cross(node a,node b,node c)//叉积，重载过的符号 { return (b-a)*(c-a); } void solve(node x)//二分搜索 { int l=0,r=n,mid,ans; while(l<=r) { mid=(r+l)/2; if(cross(wall[mid].s,wall[mid].e,x)>0)r=mid-1;//叉积判断 else l=mid+1; } arr[l-1]++; } int main() { while(scanf("%d",&n)&&n) { scanf("%d",&m); memset(arr,0,sizeof(arr)); node u1,d1; scanf("%d %d %d %d",&u1.x,&u1.y,&d1.x,&d1.y); for(int i=1;i<=n;i++) { int up,down; scanf("%d %d",&up,&down); wall[i]=Line(node(down,d1.y),node(up,u1.y)); } for(int i=1;i<=m;i++) { int dx,dy; scanf("%d %d",&dx,&dy); node now=node(dx,dy); solve(now); } for(int i=0;i<n+1;i++) { printf("%d: %d\n",i,arr[i]); } printf("\n"); } }
