Submission #915556

#	Time	Username	Problem	Language	Result	Execution time	Memory
915556		prairie2022	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1182 ms	1416 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;

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

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