1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
const int eps = 0;
int sgn(int x){
if(x == eps) return 0;
return x > eps ? 1 : -1;
}
template<typename T> struct TPoint{
T x, y;
int color;
TPoint(){}
TPoint(T _x, T _y){ x = _x; y = _y; }
TPoint(T _x, T _y, int c){ x = _x; y = _y; color = c; }
TPoint(TPoint p, int _c){ x = p.x; y = p.y; color = _c; }
friend TPoint operator +(const TPoint &a, const TPoint &b){
return TPoint(a.x + b.x, a.y + b.y);
}
friend TPoint operator -(const TPoint &a, const TPoint &b){
return TPoint(a.x - b.x, a.y - b.y);
}
friend double operator *(const TPoint &a, const TPoint &b){
return a.x * b.x + a.y * b.y;
}
friend double operator ^(const TPoint &a, const TPoint &b){
return a.x * b.y - a.y * b.x;
}
friend bool operator ==(const TPoint &a, const TPoint &b){
return abs(a.x - b.x) <= eps && abs(a.y - b.y) <= eps;
}
T len2(){
return x * x + y * y;
}
T angle(){
return atan2(y, x);
}
int toleft(const TPoint &a){
auto t = (*this) ^ a;
return (t > eps) - (t < -eps);
}
void print(){
cout << "[Point] " << x << " " << y << " " << color << '\n';
}
}; using Point = TPoint<int>;
int n, ans;
bool argcmpC(const Point &a, const Point &b){
auto Quad = [](const Point &a){
if(a.y < -eps) return 1;
if(a.y > +eps) return 4;
if(a.x < -eps) return 5;
if(a.x > +eps) return 3;
return 2;
};
int qa = Quad(a), qb = Quad(b);
if(qa != qb) return qa < qb;
auto cross = (a ^ b);
return cross > eps;
}
int querySum(int l, int r, const vector<int> &sum){
if(l > r) return 0;
if(l < 0) return sum[r];
return sum[r] - sum[l];
}
int calc(int color, int L, int R, vector<int> &sR, vector<int> &sB, vector<int> &sY){
int sum = 0;
if(color == 0){
sum = querySum(L - 1, R, sB) * querySum(L - 1, R, sY);
} else if(color == 1){
sum = querySum(L - 1, R, sR) * querySum(L - 1, R, sY);
} else{
sum = querySum(L - 1, R, sR) * querySum(L - 1, R, sB);
}
return sum;
}
void solve(vector<Point> &p, Point &Basic){
sort(p.begin(), p.end(), argcmpC);
p.insert(p.end(), p.begin(), p.end());
int siz = p.size();
vector<int> cntR(siz), cntB(siz), cntY(siz);
vector<int> sumR(siz), sumB(siz), sumY(siz);
for(int i = 0; i < siz; i++){
if(p[i].color == 0) cntR[i] = 1;
if(p[i].color == 1) cntB[i] = 1;
if(p[i].color == 2) cntY[i] = 1;
}
partial_sum(cntR.begin(), cntR.end(), sumR.begin());
partial_sum(cntB.begin(), cntB.end(), sumB.begin());
partial_sum(cntY.begin(), cntY.end(), sumY.begin());
for(int L = 0, R = 0; L < siz / 2; L++){
if(L == R) R++;
while(sgn(p[L] ^ p[R]) == 1) R++;
int sL = calc(p[L].color, L + 1, R - 1, sumR, sumB, sumY);
int sR = calc(Basic.color, R, L + siz / 2 - 1, sumR, sumB, sumY);
ans += sL * sR;
}
}
signed main(void)
{
IO;
cin >> n;
vector<Point> P(n + 5);
for(int i = 1; i <= n; i++){
int x, y, c;
cin >> x >> y >> c;
P[i] = Point(x, y, c);
}
for(int i = 1; i <= n; i++){
Point Basic = P[i];
vector<Point> np;
for(int j = 1; j <= n; j++){
if(i != j){
np.push_back(Point(P[j] - P[i], P[j].color));
}
}
solve(np, Basic);
}
cout << (ans / 2) << '\n';
return 0;
}
|
