呃。。。。很经典的题目，由于数据量较大，2分的话会比较省时间。
就是问你N个方块里面有多少个点。
so easy！
View Code 1 #include2 using namespace std; 3 int px,py; 4 struct LINE 5 { 6 int Ux, Uy, Lx, Ly; 7 }line[5002]; 8 int sum[5001]; 9 int n, m; 10 11 inline int cross(int x1, int y1, int x2, int y2) 12 { 13 return x1*y2-y1*x2; 14 } 15 16 inline bool in_box(int cnt) 17 { 18 if (cross(px-line[cnt].Lx,py-line[cnt].Ly,line[cnt].Ux-line[cnt].Lx,line[cnt].Uy-line[cnt].Ly)>0) 19 return true; 20 else 21 return false; 22 } 23 24 int main() 25 { 26 while (scanf("%d",&n) && n) 27 { 28 scanf("%d%d%d%d%d",&m,&line[0].Ux,&line[0].Uy,&line[n+1].Lx,&line[n+1].Ly); 29 line[0].Lx = line[0].Ux; 30 line[0].Ly = line[n+1].Ly; 31 line[n+1].Ux = line[n+1].Lx; 32 line[n+1].Uy = line[0].Uy; 33 sum[0] = 0; 34 for (int i(1); i<=n; ++i) 35 { 36 scanf("%d%d",&line[i].Ux,&line[i].Lx); 37 line[i].Uy = line[0].Uy; 38 line[i].Ly = line[n+1].Ly; 39 sum[i] = 0; 40 } 41 for (int k(1); k<=m; ++k) 42 { 43 scanf("%d%d",&px,&py); 44 int l(0); 45 int r(n+1); 46 while (l <= r) 47 { 48 int mid = (l + r) >> 1; 49 if (in_box(mid)) 50 { 51 if (l+1 == r) 52 { 53 sum[mid]++; 54 break; 55 } 56 l = mid; 57 } 58 else 59 { 60 if (l+1 == r) 61 { 62 sum[mid]++; 63 break; 64 } 65 r = mid; 66 } 67 } 68 } 69 for (int i(0); i<=n; ++i) 70 { 71 printf("%d: %d\n",i,sum[i]); 72 } 73 printf("\n"); 74 } 75 return 0; 76 }