BZOJ1914 [Usaco2010 OPen]Triangle Counting 数三角形

  1 2
  2 3
  3 4
  4 5
  5 6
  6 7
  7 8
  8 9
  9 10
 10 11
 11 12
 12 13
 13 14
 14 15
 15 16
 16 17
 17 18
 18 19
 19 20
 20 21
 21 22
 22 23
 23 24
 24 25
 25 26
 26 27
 27 28
 28 29
 29 30
 30 31
 31 32
 32 33
 33 34
 34 35
 35 36
 36 37
 37 38
 38 39
 39 40
 40 41
 41 42
 42 43
 43 44
 44 45
 45 46
 46 47
 47 48
 48 49
 49 50
 50 51
 51 52
 52 53
 53 54
 54 55
 55 56
 56 57
 57 58
 58 59
 59 60
 60 61
 61 62
 62 63
 63 64
 64 65
 65 66
 66 67
 67 68
 68 69
 69 /**************************************************************
 70     Problem: 1914
 71     User: rausen
 72     Language: C++
 73     Result: Accepted
 74     Time:88 ms
 75     Memory:3160 kb
 76 ****************************************************************/
 77  
 78 #include <cstdio>
 79 #include <cmath>
 80 #include <algorithm>
 81  
 82 using namespace std;
 83 typedef long long ll;
 84 typedef double lf;
 85 const int N = 100005;
 86  
 87 int n;
 88 ll cnt = 0;
 89  
 90 struct P {
 91     ll x, y;
 92     lf an;
 93     P() {}
 94     P(ll _x, ll _y, lf _an) : x(_x), y(_y), an(_an) {}
 95 }a[N];
 96 inline bool operator < (const P &a, const P &b) {
 97     return a.an < b.an;
 98 }
 99 inline ll operator * (const P &a, const P &b) {
100     return (ll) a.x * b.y - a.y * b.x;
101 }
102  
103 inline int read() {
104     int x = 0, sgn = 1;
105     char ch = getchar();
106     while (ch < ‘0‘ || ‘9‘ < ch) {
107         if (ch == ‘-‘) sgn = -1;
108         ch = getchar();
109     }
110     while (‘0‘ <= ch && ch <= ‘9‘) {
111         x = x * 10 + ch - ‘0‘;
112         ch = getchar();
113     }
114     return sgn * x;
115 }
116  
117 void work() {
118     int r = 1, t = 0, i;
119     for (i = 1; i <= n; ++i) {
120         while ((r % n + 1) != i && a[i] * a[r % n + 1] >= 0) ++t, ++r;
121         cnt += (ll) t * (t - 1) / 2;
122         --t;
123     }
124 }
125  
126 int main() {
127     n = read();
128     int i, X, Y;
129     for (i = 1; i <= n; ++i) {
130         X = read(), Y = read();
131         a[i] = P(X, Y, atan2(Y, X));
132     }
133     sort(a + 1, a + n + 1);
134     work();
135     printf("%lld\n", (ll) n * (n - 1) * (n - 2) / 6 - cnt);
136     return 0;
137 }

 1 /**************************************************************
 2     Problem: 1914
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:60 ms
 7     Memory:4728 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13  
14 using namespace std;
15 typedef long long ll;
16 typedef double lf;
17 const int N = 100005;
18 const int Maxbuf = 1600005;
19 int n;
20 ll cnt = 0, Left = 0, len;
21 char buf[Maxbuf];
22  
23 struct P {
24     ll x, y;
25     lf an;
26     P() {}
27     P(ll _x, ll _y, lf _an) : x(_x), y(_y), an(_an) {}
28 }a[N];
29 inline bool operator < (const P &a, const P &b) {
30     return a.an < b.an;
31 }
32 inline ll operator * (const P &a, const P &b) {
33     return (ll) a.x * b.y - a.y * b.x;
34 }
35  
36 inline int read() {
37     int x = 0, sgn = 1;
38     while (buf[Left] < ‘0‘ || ‘9‘ < buf[Left]) {
39         if (buf[Left] == ‘-‘) sgn = -1;
40         ++Left;
41     }
42     while (‘0‘ <= buf[Left] && buf[Left] <= ‘9‘) {
43         x = x * 10 + buf[Left] - ‘0‘;
44         ++Left;
45     }
46     return sgn * x;
47 }
48  
49 void work() {
50     int r = 1, t = 0, i;
51     for (i = 1; i <= n; ++i) {
52         while ((r % n + 1) != i && a[i] * a[r % n + 1] >= 0) ++t, ++r;
53         cnt += (ll) t * (t - 1) / 2;
54         --t;
55     }
56 }
57  
58 int main() {
59     len = fread(buf, 1, Maxbuf, stdin);
60     buf[len] = ‘ ‘;
61     n = read();
62     int i, X, Y;
63     for (i = 1; i <= n; ++i) {
64         X = read(), Y = read();
65         a[i] = P(X, Y, atan2(Y, X));
66     }
67     sort(a + 1, a + n + 1);
68     work();
69     printf("%lld\n", (ll) n * (n - 1) * (n - 2) / 6 - cnt);
70     return 0;
71 }