# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
157228 | combi1k1 | 별자리 2 (JOI14_constellation2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef pair<int,ii> poi;
vector<poi> Star;
bool cmp(poi A,poi B) {
int xa = A.Y.X;
int ya = A.Y.Y;
int xb = B.Y.X;
int yb = B.Y.Y;
return 1int* xa * yb >= 1int* ya * xb;
}
int cntLef[3];
int cntRig[3];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for(int i = 0 ; i < n ; ++i) {
int x; cin >> x;
int y; cin >> y;
int c; cin >> c;
Star.push_back(poi(c,{x,y}));
}
int ans = 0;
for(poi O : Star) {
vector<poi> lef;
vector<poi> rig;
memset(cntLef,0,sizeof cntLef);
memset(cntRig,0,sizeof cntRig);
for(poi P : Star) if (P != O) {
P.Y.X -= O.Y.X;
P.Y.Y -= O.Y.Y;
if (P.Y > ii(0,0))
rig.push_back(P),
cntRig[P.X]++;
if (P.Y < ii(0,0))
P.Y.X = -P.Y.X,
P.Y.Y = -P.Y.Y,
lef.push_back(P),
cntLef[P.X]++;
}
sort(all(lef),cmp);
sort(all(rig),cmp);
int ptr = 0;
for(poi P : rig) {
cntRig[P.X]--;
cntLef[P.X]++;
while(ptr < sz(lef) && cmp(lef[ptr],P))
cntRig[lef[ptr].X]++,
cntLef[lef[ptr].X]--,
ptr++;
int cur = 1;
for(int i = 0 ; i < 3 ; ++i) {
if (i != O.X) cur *= cntRig[i];
if (i != P.X) cur *= cntLef[i];
}
ans += cur;
}
}
cout << ans << endl;
}