题目链接：https://vjudge.net/problem/POJ-2318
题意：有n条线将矩形分成n+1块，m个点落在矩形内，求每一块点的个数。
思路：
最近开始肝计算几何，之前的几何题基本处于挂机状态，但听别人说几何题不会太难，所以打算把几何给过了。
先引入叉积的一个重要性质，O为原点：
OP^OQ>0 : P在Q的顺时针方向。
OP^OQ<0 : P在Q的逆时针方向。
OP^OQ=0 : O,P,Q共线。
那么我们就可以利用该性质判断一个点P在直线AB的左侧当且仅当：PA^PB<0。
再发现可以用二分查找第一条满足点在直线左侧的直线即可，其单调性显然可知。
AC code：
#include<cstdio> #include<algorithm> using namespace std; const int maxn=5005; int n,m,x1,y1,x2,y2,ans[maxn],flag=1; struct Point{ int x,y; Point(){} Point(int xx,int yy):x(xx),y(yy){} Point operator + (const Point& b)const{ return Point(x+b.x,y+b.y); } Point operator - (const Point& b)const{ return Point(x-b.x,y-b.y); } int operator * (const Point& b)const{ return x*b.x+y*b.y; } int operator ^ (const Point& b)const{ return x*b.y-b.x*y; } }; struct Line{ Point s,e; Line(){}; Line(Point ss,Point ee){ s=ss,e=ee; } }line[maxn]; int check(int x,int y,int m){ Point pt=Point(x,y); return (line[m].s-pt)^(line[m].e-pt); } int main(){ while(scanf("%d",&n),n){ if(flag) flag=0; else printf("\n"); scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2); for(int i=0;i<=n;++i) ans[i]=0; for(int i=0;i<n;++i){ int u,l; scanf("%d%d",&u,&l); line[i]=Line(Point(u,y1),Point(l,y2)); } line[n]=Line(Point(x2,y1),Point(x2,y2)); while(m--){ int x,y; scanf("%d%d",&x,&y); Point pt=Point(x,y); int l=0,r=n,mid; while(l<=r){ mid=(l+r)>>1; if(check(x,y,mid)<=0) r=mid-1; else l=mid+1; } ++ans[l]; } for(int i=0;i<=n;++i) printf("%d: %d\n",i,ans[i]); } }
转载于:https://www.cnblogs.com/FrankChen831X/p/11471321.html
