题目大意：2318：给定一个矩形和n条边（由上到下，不想交），这些边把矩形分成n+1块（0 ~n）。。问给M个点，每块区域有多少个点。。
2398：差不多，只是给定的线段未排序。。还有输出变成输出相同点数的个数。。
比如 0~N：1，1，2，1，3
那么输出：Box
1：3
2：1
3：1
思路：简单的点与线断的判断，用叉乘解决。。
code2318
1 /* 2 State:Accepted 3 Time:2013-03-24 20:57:09 4 */ 5 6 #include<iostream> 7 #include<cstring> 8 #include<string> 9 #include<fstream> 10 #include<cmath> 11 #include<algorithm> 12 using namespace std; 13 int n,m,x1,y_1,x2,y2; 14 int b[6000][3], a[6000][3], pos[6000]; 15 16 void init(){ 17 scanf("%d%d%d%d%d", &m, &x1, &y_1, &x2, &y2); 18 for (int i = 1; i <= n; ++i) 19 scanf("%d%d",&a[i][0], &a[i][1]); 20 for (int i = 1; i <= m; ++i) 21 scanf("%d%d",&b[i][0], &b[i][1]); 22 } 23 24 bool check(int x1, int y1, int x2, int y2){ 25 if (x1*y2 - x2*y1 > 0) return true; 26 return false; 27 } 28 29 void solve(){ 30 bool flag; 31 memset(pos , 0 , sizeof(pos)); 32 for (int i = 1; i <= m ;++i){ 33 flag = false; 34 for (int j = 1; j <= n; ++j) 35 if (check(a[j][0] - a[j][1] , y_1 - y2, b[i][0] - a[j][1],b[i][1] - y2)){ 36 ++pos[j - 1]; 37 flag = true; 38 break; 39 } 40 if (!flag) ++pos[n]; 41 } 42 for (int i = 0; i <= n ; ++i) 43 printf("%d: %d\n",i , pos[i]); 44 printf("\n"); 45 } 46 47 int main(){ 48 freopen("poj2318.in","r",stdin); 49 freopen("poj2318.out","w",stdout); 50 while (scanf("%d",&n)!=EOF && n){ 51 init(); 52 solve(); 53 } 54 fclose(stdin); fclose(stdout); 55 }
code2398
1 /* 2 State:Accepted 3 Time:2013-03-24 21:43:48 4 */ 5 #include<iostream> 6 #include<cstring> 7 #include<string> 8 #include<fstream> 9 #include<cmath> 10 #include<algorithm> 11 using namespace std; 12 int n,m; 13 long long x1,y_1,x2,y2; 14 long long b[6000][3], a[6000][3]; 15 int pos[6000], res[1500]; 16 17 void init(){ 18 scanf("%d%I64d%I64d%I64d%I64d", &m, &x1, &y_1, &x2, &y2); 19 for (int i = 1; i <= n; ++i) 20 scanf("%I64d%I64d",&a[i][0], &a[i][1]); 21 for (int i = 1; i <= n ;++i) 22 for (int j = i + 1; j <=n ; ++j) 23 if (a[i][0] > a[j][0]){ 24 a[0][0] = a[i][0]; a[0][1] = a[i][1]; 25 a[i][0] = a[j][0]; a[i][1] = a[j][1]; 26 a[j][0] = a[0][0]; a[j][1] = a[0][1]; 27 } 28 for (int i = 1; i <= m; ++i) 29 scanf("%I64d%I64d",&b[i][0], &b[i][1]); 30 } 31 32 bool check(long long x1, long long y1, long long x2, long long y2){ 33 if (x1*y2 - x2*y1 > 0) return true; 34 return false; 35 } 36 37 void solve(){ 38 bool flag; 39 memset(pos , 0 , sizeof(pos)); 40 for (int i = 1; i <= m ;++i){ 41 flag = false; 42 for (int j = 1; j <= n; ++j) 43 if (check(a[j][0] - a[j][1] , y_1 - y2, b[i][0] - a[j][1],b[i][1] - y2)){ 44 ++pos[j - 1]; 45 flag = true; 46 break; 47 } 48 if (!flag) ++pos[n]; 49 } 50 printf("Box\n"); 51 memset(res, 0 ,sizeof(res)); 52 for (int i = 0; i <= n ; ++i) 53 ++res[pos[i]]; 54 for (int i = 1; i<= n; ++i) 55 if (res[i]) printf("%d: %d\n",i ,res[i]); 56 } 57 58 int main(){ 59 freopen("poj2398.in","r",stdin); 60 freopen("poj2398.out","w",stdout); 61 while (scanf("%d",&n)!=EOF && n){ 62 init(); 63 solve(); 64 } 65 fclose(stdin); fclose(stdout); 66 }