LA 4064 (计数 极角排序) Magnetic Train Tracks

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int maxn = 1200 + 10;
 8 const double PI = acos(-1.0);
 9 const double eps = 1e-9;
10 
11 struct Point
12 {
13     double x, y;
14     Point() {}
15     Point(double x, double y):x(x), y(y) {}
16 }p[maxn], p2[maxn];
17 
18 Point operator - (const Point& A, const Point& B)
19 {
20     return Point(A.x-B.x, A.y-B.y);
21 }
22 
23 double ang[maxn * 2];
24 
25 LL inline C3(int n) { return (LL)n * (n-1) / 2 * (n-2) / 3; }
26 
27 int main()
28 {
29     //freopen("in.txt", "r", stdin);
30     int n, kase = 0;
31 
32     while(scanf("%d", &n) == 1 && n)
33     {
34         for(int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
35 
36         LL cnt = 0;
37         for(int i = 0; i < n; i++)
38         {
39             int k = 0;
40             for(int j = 0; j < n; j++) if(j != i)
41             {
42                 p2[k] = p[j] - p[i];
43                 ang[k] = atan2(p2[k].y, p2[k].x);
44                 ang[k + n - 1] = ang[k] + PI * 2.0;
45                 k++;
46             }
47             k = 2*n-2;
48             sort(ang, ang + k);
49             int L, R1 = 0, R2 = 0;
50             for(L = 0; L < n-1; L++)
51             {
52                 double b1 = ang[L] + PI / 2;
53                 double b2 = ang[L] + PI;
54                 while(ang[R1] <= b1 - eps) R1++;
55                 while(ang[R2] < b2) R2++;
56                 cnt += R2 - R1;
57             }
58         }
59         LL ans = C3(n) - cnt;
60         printf("Scenario %d:\nThere are %lld sites for making valid tracks\n", ++kase, ans);
61     }
62 
63     return 0;
64 }