首页 > 代码库 > POJ 2318 TOYS（叉积+二分or暴力）

POJ 2318 TOYS（叉积+二分or暴力）

2024-07-04 18:01:42   223人阅读

题目链接：POJ 2318 TOYS

【写在前面】前几天跟队友分了方向，学渣开始进行计算几何的专题了，真是脑壳有点痛啊。但是我想做多了就没这么坑爹了睡觉

【题意】大体意思就是给你一个矩形，有被若干直线分成N个格子，给出M个点的坐标，问你每个点位于哪个格子中。

【思路】其实就是点在凸四边形内的判断，然后就可以利用叉积的性质，当然可以用暴力枚举也可以过，但是时间复杂度有点高，最好是用二分求解。（一直觉得二分真是牛逼啊）

下面贴AC代码，用二分219MS就过了：

 1 /*
 2 ** POJ 2318 TOYS
 3 ** Created by Rayn @@ 2014/05/04
 4 */
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <algorithm>
 8 using namespace std;
 9 const int MAX = 5010;
10 const int INF = 0x3f3f3f3f;
11 
12 struct Point {
13     double x, y;
14     Point(double a=0, double b=0): x(a), y(b) {}
15 } dot[MAX];
16 
17 double up[MAX], low[MAX];
18 int ans[MAX];
19 
20 double Cross(Point A, Point B, Point C)
21 {
22     return (C.x-A.x)*(B.y-A.y)-(B.x-A.x)*(C.y-A.y);
23 }
24 int main()
25 {
26 #ifdef _Rayn
27     freopen("in.txt", "r", stdin);
28 #endif
29 
30     int n, m, first = 1;
31     double x1, y1, x2, y2;
32 
33     while(scanf("%d", &n) != EOF && n)
34     {
35         if(!first)
36             printf("\n");
37         first = 0;
38 
39         scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);
40         for(int i=0; i<n; ++i)
41         {
42             scanf("%lf%lf", &up[i], &low[i]);
43         }
44         up[n] = low[n] = x2; //最后一条，矩形的右边(x2,y1),(x2,y2)，方便判断;
45 
46         //强大的二分
47         memset(ans, 0, sizeof(ans));
48         for(int i=0; i<m; ++i)
49         {
50             scanf("%lf%lf", &dot[i].x, &dot[i].y);
51             int left = 0, right = n, mid = 0;
52             while(left <= right)
53             {
54                 mid = (left + right) / 2;
55                 Point b(low[mid], y2), c(up[mid], y1);
56                 if(Cross(dot[i], b, c) > 0)
57                     left = mid + 1;
58                 else
59                     right = mid - 1;
60             }
61             ans[left]++;
62         }
63         for(int i=0; i<=n; ++i)
64             printf("%d: %d\n", i, ans[i]);
65     }
66     return 0;
67 }
View Code

 


联系
我们