#include<bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
typedef long long ll;
typedef pair<pair<ll, ll>, int> pll;
#define F first.first
#define S first.second
#define C second
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(make_pair(-1ll, 0ll), 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 |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 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 |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
348 KB |
Output is correct |
| 5 |
Correct |
4 ms |
348 KB |
Output is correct |
| 6 |
Correct |
9 ms |
348 KB |
Output is correct |
| 7 |
Correct |
9 ms |
348 KB |
Output is correct |
| 8 |
Correct |
9 ms |
344 KB |
Output is correct |
| 9 |
Correct |
10 ms |
348 KB |
Output is correct |
| 10 |
Correct |
7 ms |
348 KB |
Output is correct |
| 11 |
Correct |
9 ms |
348 KB |
Output is correct |
| 12 |
Correct |
9 ms |
496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
71 ms |
348 KB |
Output is correct |
| 2 |
Correct |
97 ms |
540 KB |
Output is correct |
| 3 |
Correct |
111 ms |
344 KB |
Output is correct |
| 4 |
Correct |
111 ms |
556 KB |
Output is correct |
| 5 |
Correct |
282 ms |
648 KB |
Output is correct |
| 6 |
Correct |
527 ms |
692 KB |
Output is correct |
| 7 |
Correct |
897 ms |
876 KB |
Output is correct |
| 8 |
Correct |
1277 ms |
1328 KB |
Output is correct |
| 9 |
Correct |
1271 ms |
840 KB |
Output is correct |
| 10 |
Correct |
1290 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
1266 ms |
1092 KB |
Output is correct |
| 12 |
Correct |
1251 ms |
1052 KB |
Output is correct |
| 13 |
Correct |
1300 ms |
1700 KB |
Output is correct |
| 14 |
Correct |
1278 ms |
912 KB |
Output is correct |
| 15 |
Correct |
1248 ms |
848 KB |
Output is correct |
| 16 |
Correct |
1277 ms |
988 KB |
Output is correct |
