题意：判断点是否在凸多边形内
#include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; #define eps 1e-8 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0)) struct point { int x,y; point() { } point(int xx,int yy) { x=xx; y=yy; } } p[2005],w[5],A,B; struct node { point a,b; } d[2005]; bool cmp(node A,node B) { return A.a.x<B.a.x; } double cross(point a,point b,point c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } int inside_convex(point q,int n) { int i,s[3]= {1,1,1}; for (i=0; i<n&&s[1]|s[2]; i++) s[_sign(cross(w[i],w[(i+1)%n],q))]=0; return s[1]|s[2]; } void solve(int id) { w[0]=d[id-1].a; w[1]=d[id-1].b; w[2]=d[id].b; w[3]=d[id].a; } int f[2005]; int t[2005]; int main() { int T,i,j,k,m,n; while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(t,0,sizeof(t)); memset(f,0,sizeof(f)); scanf("%d",&m); scanf("%d%d",&A.x,&A.y); scanf("%d%d",&B.x,&B.y); d[0].a=A; d[0].b=point(A.x,B.y); for(i=1; i<=n; i++) { scanf("%d%d",&d[i].a.x,&d[i].b.x); d[i].a.y=A.y; d[i].b.y=B.y; } d[i].a=point(B.x,A.y); d[i].b=B; n+=2; sort(d,d+n,cmp); for(i=0;i<m;i++) scanf("%d%d",&p[i].x,&p[i].y); for(i=1;i<n;i++) { solve(i); for(j=0;j<m;j++) if(inside_convex(p[j],4)) f[i]++; } for(i=0;i<2001;i++) t[f[i]]++; printf("Box "); for(i=1;i<2001;i++) if(t[i]) printf("%d: %d ",i,t[i]); } }