#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
struct pnt{
int x, y, c;
}a[3005];
int n;
lint ccw(pnt a, pnt b, pnt c){
int dx1 = b.x - a.x;
int dy1 = b.y - a.y;
int dx2 = c.x - a.x;
int dy2 = c.y - a.y;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
int main(){
cin >> n;
for(int i=0; i<n; i++){
cin >> a[i].x >> a[i].y >> a[i].c;
}
lint ret = 0;
for(int i=0; i<n; i++){
int cl[3] = {}, cr[3] = {};
vector<pnt> v;
for(int j=0; j<n; j++){
if(i != j) v.push_back(a[j]);
}
sort(v.begin(), v.end(), [&](const pnt &p, const pnt &q){
if(p.y == a[i].y && p.x > a[i].x) return true;
if(q.y == a[i].y && q.x > a[i].x) return false;
if(1ll * (a[i].y - p.y) * (a[i].y - q.y) <= 0) return p.y > q.y;
return ccw(a[i], p, q) > 0;
});
for(int i=0; i<n-1; i++){
cr[v[i].c]++;
v.push_back(v[i]);
}
int p = 0;
for(int j=0; j<n-1; j++){
while(p < n-1+j && ccw(a[i], v[j], v[p]) >= 0){
cl[v[p].c]++;
cr[v[p].c]--;
p++;
}
cl[v[j].c]--;
lint tret = 1;
for(int k=0; k<3; k++){
if(a[i].c != k) tret *= cl[k];
if(v[j].c != k) tret *= cr[k];
}
ret += tret;
cr[v[j].c]++;
}
}
cout << ret / 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1760 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1760 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1760 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1760 KB |
Output is correct |
| 7 |
Correct |
14 ms |
1760 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1760 KB |
Output is correct |
| 9 |
Correct |
13 ms |
1760 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1760 KB |
Output is correct |
| 11 |
Correct |
14 ms |
1760 KB |
Output is correct |
| 12 |
Correct |
14 ms |
1760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
1760 KB |
Output is correct |
| 2 |
Correct |
129 ms |
1760 KB |
Output is correct |
| 3 |
Correct |
164 ms |
1760 KB |
Output is correct |
| 4 |
Correct |
165 ms |
1760 KB |
Output is correct |
| 5 |
Correct |
386 ms |
1760 KB |
Output is correct |
| 6 |
Correct |
676 ms |
1760 KB |
Output is correct |
| 7 |
Correct |
1222 ms |
1948 KB |
Output is correct |
| 8 |
Correct |
1688 ms |
1948 KB |
Output is correct |
| 9 |
Correct |
1668 ms |
1948 KB |
Output is correct |
| 10 |
Correct |
1597 ms |
1948 KB |
Output is correct |
| 11 |
Correct |
1682 ms |
1948 KB |
Output is correct |
| 12 |
Correct |
1585 ms |
1948 KB |
Output is correct |
| 13 |
Correct |
1628 ms |
1948 KB |
Output is correct |
| 14 |
Correct |
1638 ms |
1948 KB |
Output is correct |
| 15 |
Correct |
1644 ms |
1948 KB |
Output is correct |
| 16 |
Correct |
1646 ms |
1948 KB |
Output is correct |
