poj 2318 TOYS (几何+二分)

　　在别人的几何练习中找出来的简单的几何加二分的题目。题意是，给出隔槽的构造，统计出给出的点在哪一个隔槽中，最后将所有的统计结果输出来。

　　主要是不能用cin cout输入输出大量数据。这里用double也不会超时，不过用int会快很多。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 struct Point {
11     double x, y;
12     Point() {}
13     Point(double x, double y) : x(x), y(y) {}
14 } ;
15 template<class T> T sqr(T x) { return x * x;}
16 inline double ptDis(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
17 
18 typedef Point Vec;
19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
23 
24 const double EPS = 1e-10;
25 const double PI = acos(-1.0);
26 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
27 bool operator < (Point a, Point b) { return sgn(a.x - b.x) < 0 || sgn(a.x - b.x) == 0 && a.y < b.y;}
28 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;}
29 
30 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
31 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
32 inline double crossDet(Vec o, Vec a, Vec b) { return crossDet(a - o, b - o);}
33 inline bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(x, a, b)) == 0 && sgn(dotDet(a - x, b - x)) < 0;}
34 
35 int ptInPoly(Point p, Point *poly, int n) {
36     int wn =  0;
37     poly[n] = poly[0];
38     for (int i = 0; i < n; i++) {
39         if (onSeg(p, poly[i], poly[i + 1])) return -1;
40         int k = sgn(crossDet(poly[i], poly[i + 1], p));
41         int d1 = sgn(poly[i].y - p.y);
42         int d2 = sgn(poly[i + 1].y - p.y);
43         if (k > 0 && d1 <= 0 && d2 > 0) wn++;
44         if (k < 0 && d2 <= 0 && d1 > 0) wn--;
45     }
46     return wn != 0;
47 }
48 
49 const int N = 5555;
50 double x[N][2], X1, Y1, X2, Y2;
51 int cnt[N];
52 Point p[10];
53 
54 void insert(double X, double Y, int n) {
55     int h = 0, t = n, m, ok = -1;
56     Point cur = Point(X, Y);
57     while (h <= t) {
58         m = h + t >> 1;
59         p[0] = Point(X1, Y2);
60         p[1] = Point(X1, Y1);
61         p[2] = Point(x[m][1], Y1);
62         p[3] = Point(x[m][0], Y2);
63         bool front = ptInPoly(cur, p, 4);
64         if (front) ok = m, t = m - 1;
65         else h = m + 1;
66     }
67     if (ok == -1) { puts("shit~"); return ;}
68     cnt[ok]++;
69 }
70 
71 int main() {
72     int n, m;
73     bool pnt = false;
74     while (cin >> n && n) {
75         cin >> m;
76         if (pnt) puts("");
77         pnt = true;
78         cin >> X1 >> Y1 >> X2 >> Y2;
79         if (X1 > X2) swap(X1, X2);
80         if (Y1 > Y2) swap(Y1, Y2);
81         for (int i = 0; i < n; i++) {
82             for (int j = 0; j < 2; j++) {
83                 scanf("%lf", &x[i][j]);
84             }
85         }
86         x[n][0] = x[n][1] = X2;
87         memset(cnt, 0, sizeof(cnt));
88         double x, y;
89         for (int i = 0; i < m; i++) {
90             scanf("%lf%lf", &x, &y);
91             insert(x, y, n);
92         }
93         for (int i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);
94     }
95     return 0;
96 }
97 
98

View Code

——written by Lyon