#include<bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
typedef long long ll;
struct pll{
ll F, S;
int C;
pll(){}
pll(ll F, ll S, int C) : F(F), S(S), C(C){}
};
inline pll operator-(pll p1, pll p2){
return {p1.F-p2.F, p1.S-p2.S, p1.C};
}
inline ll dot(pll p1, pll p2){
return p1.F*p2.F+p1.S*p2.S;
}
inline ll cross(pll p1, pll p2){
return p1.F*p2.S-p1.S*p2.F;
}
inline int sign(ll n){
return n?(n>0?1:-1):0;
}
inline bool is_neg(pll p){
return p.S<0 || (!p.S && p.F<0);
}
inline bool cmp(pll p1, pll p2){
bool b1 = is_neg(p1), b2 = is_neg(p2);
if(b1!=b2) return b1<b2;
ll area = cross(p1, p2);
return area?area>0:(abs(p1.F)<abs(p2.F) || abs(p1.S)<abs(p2.S));
}
int main(){
fastio
int n;
ll ans = 0;
cin >> n;
vector<pll> p(n);
for(int i=0; i<n; i++) cin >> p[i].F >> p[i].S >> p[i].C;
n--;
for(int i=0; i<=n; i++){
vector<pll> q;
for(int j=0; j<=n; j++)
if(j!=i) q.push_back(p[j]-p[i]);
sort(q.begin(), q.end(), cmp);
int cnt0[3], cnt1[3]; // cnt0 with origin, cnt1 with polar angle
memset(cnt0, 0, sizeof(cnt0)), memset(cnt1, 0, sizeof(cnt1));
for(const pll &qq: q){
if(is_neg(qq)) cnt1[qq.C]++;
else cnt0[qq.C]++;
}
int k = lower_bound(q.begin(), q.end(), pll(-1, 0, 0), cmp)-q.begin();
q.resize(n<<1);
copy(q.begin(), q.begin()+n, q.begin()+n);
for(int j=0; j<n; j++){
cnt1[q[j].C]++, cnt0[q[j].C]--;
while(j==k || cross(q[j], q[k])>0){
cnt0[q[k].C]++, cnt1[q[k].C]--, k++;
}
ans += 1ll*cnt0[(p[i].C+1)%3]*cnt0[(p[i].C+2)%3]*cnt1[(q[j].C+1)%3]*cnt1[(q[j].C+2)%3];
}
}
cout << (ans>>1) << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
452 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
4 ms |
348 KB |
Output is correct |
| 6 |
Correct |
10 ms |
344 KB |
Output is correct |
| 7 |
Correct |
9 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
348 KB |
Output is correct |
| 9 |
Correct |
9 ms |
344 KB |
Output is correct |
| 10 |
Correct |
6 ms |
348 KB |
Output is correct |
| 11 |
Correct |
9 ms |
460 KB |
Output is correct |
| 12 |
Correct |
9 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
65 ms |
348 KB |
Output is correct |
| 2 |
Correct |
89 ms |
560 KB |
Output is correct |
| 3 |
Correct |
101 ms |
344 KB |
Output is correct |
| 4 |
Correct |
101 ms |
348 KB |
Output is correct |
| 5 |
Correct |
276 ms |
912 KB |
Output is correct |
| 6 |
Correct |
475 ms |
712 KB |
Output is correct |
| 7 |
Correct |
811 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
1167 ms |
1296 KB |
Output is correct |
| 9 |
Correct |
1160 ms |
1416 KB |
Output is correct |
| 10 |
Correct |
1150 ms |
1156 KB |
Output is correct |
| 11 |
Correct |
1163 ms |
1208 KB |
Output is correct |
| 12 |
Correct |
1146 ms |
928 KB |
Output is correct |
| 13 |
Correct |
1182 ms |
904 KB |
Output is correct |
| 14 |
Correct |
1150 ms |
1176 KB |
Output is correct |
| 15 |
Correct |
1163 ms |
1020 KB |
Output is correct |
| 16 |
Correct |
1171 ms |
892 KB |
Output is correct |
