Submission #915558

#	Time	Username	Problem	Language	Result	Execution time	Memory
915558		prairie2022	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1300 ms	1700 KiB

constellation2

#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;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45