题意：
给定一些线段的两端和一些点。
问某些区域出现的点的个数的次数。。。
题目给定的线段未排序！！！
View Code
1 /* 2 几何+排序 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 using namespace std; 10 const int maxn = 1005; 11 const double eps = 1e-8; 12 struct point { 13 double x,y; 14 }; 15 struct Line { 16 point u,d; 17 }line[ maxn ]; 18 int cnt[ maxn ],vis[ maxn ]; 19 double xmult( point sp,point ep,point op ){ 20 return ( sp.x-op.x )*( ep.y-op.y )-( sp.y-op.y )*( ep.x-op.x ); 21 } 22 int cmp( Line a,Line b ){ 23 return ( a.u.x+a.d.x )<( b.u.x+b.d.x ); 24 } 25 int main(){ 26 int n,m; 27 double x1,x2,y1,y2; 28 while( scanf("%d",&n),n ){ 29 scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2); 30 line[ 0 ].u.x = x1,line[ 0 ].u.y = y1; 31 line[ 0 ].d.x = x1,line[ 0 ].d.y = y2; 32 for( int i=1;i<=n;i++ ){ 33 scanf("%lf%lf",&line[ i ].u.x,&line[ i ].d.x); 34 line[ i ].u.y = y1; 35 line[ i ].d.y = y2; 36 } 37 sort( line+1,line+n+1,cmp ); 38 line[ n+1 ].u.x = x2,line[ n+1 ].u.y = y1; 39 line[ n+1 ].d.x = x2,line[ n+1 ].d.y = y2; 40 memset( cnt,0,sizeof( cnt ) ); 41 memset( vis,0,sizeof( vis ) ); 42 for( int num=0;num<m;num++ ){ 43 point toy; 44 scanf("%lf%lf",&toy.x,&toy.y); 45 for( int j=0;j<=n;j++ ){ 46 if( xmult( toy,line[ j ].d,line[ j ].u )<-eps&&xmult( toy,line[ j+1 ].d,line[ j+1 ].u )>eps ){ 47 cnt[ j ]++; 48 } 49 } 50 } 51 for( int i=0;i<=n;i++ ){ 52 if( cnt[ i ]!=0 ) 53 vis[ cnt[i] ]++; 54 } 55 printf("Box\n"); 56 for( int i=1;i<maxn;i++ ){ 57 if( vis[ i ]!=0 ) 58 printf("%d: %d\n",i,vis[ i ]); 59 } 60 } 61 return 0; 62 }