题目链接：http://poj.org/problem?id=2318
题目大意：给定一个矩形，矩形被n条线段划分成n+1个区域，给出m个点，求每个区域中有几个点。（具体输入输出看题目去吧）
思路：二分，用叉积判断点在线段左边还是右边，应该是道简单题吧
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<ctime> #include<queue> #include<map> #include<set> #include<vector> #define sqr(x) (x)*(x) #define rep(i,x,y) for (int i=(x);i<=(y);i++) #define per(i,x,y) for (int i=(x);i>=(y);i--) typedef long long LL; typedef double DBD; using namespace std; const int inf=1e9; const LL INF=1e18; const int N=5010; LL n,m,maxx,minx,maxy,miny,a[N],b[N],Ans[N]; int Write[20]; int read() {int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} LL read_LL() {LL d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} void write(int x){int t=0; if (x<0) putchar('-'),x=-x; for (;x;x/=10) Write[++t]=x%10; if (!t) putchar('0'); for (int i=t;i>=1;i--) putchar((char)(Write[i]+48));} void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);} LL cross(LL a,LL b,LL c,LL d,LL e,LL f){return (e-a)*(d-b)-(c-a)*(f-b);} int main() { //judge(); while (1) { n=read_LL(); if (n==0) break; rep(i,0,n) Ans[i]=0; m=read_LL(); minx=read_LL(); maxy=read_LL(); maxx=read_LL(); miny=read_LL(); rep(i,1,n) a[i]=read_LL(),b[i]=read_LL(); a[++n]=maxx; b[n]=maxx; rep(i,1,m) { LL x=read_LL(),y=read_LL(); int l=1,r=n,ans=0; while (l<=r) { int mid=(l+r)>>1; if (cross(b[mid],miny,x,y,a[mid],maxy)>=0) ans=mid,r=mid-1; else l=mid+1; } Ans[ans-1]++; } rep(i,0,n-1) printf("%d: %d ",i,Ans[i]); puts(""); } return 0; }
被输出格式坑了。。。原来两组输出之间要空行。。。