Submission #173482

#	Time	Username	Problem	Language	Result	Execution time	Memory
173482		jhwest2	별자리 2 (JOI14_constellation2)	C++14	55 / 100	9039 ms	504 KiB

constellation2

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
ll X[3030], Y[3030], C[3030];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N;
	for (int i=0; i<N; i++) {
		cin >> X[i] >> Y[i] >> C[i];
	}

	ll ans = 0;
	for (int i=0; i<N; i++) {
		for (int j=i+1; j<N; j++) {
			int cnt[3][2]; memset(cnt, 0, sizeof cnt);
			for (int k=0; k<N; k++) {
				ll t = (X[k]-X[i])*(Y[j]-Y[i]) - (X[j]-X[i])*(Y[k]-Y[i]);

				if (t == 0) continue;
				t = t>0 ? 0 : 1;
				cnt[C[k]][t]++;
			}

			ll li=1, lj=1, ri=1, rj=1;
			for (int k=0; k<3; k++) {
				if (C[i] != k) li *= cnt[k][0], ri *= cnt[k][1];
				if (C[j] != k) lj *= cnt[k][0], rj *= cnt[k][1];
			}
			ans += li*rj + lj*ri;
		}
	}

	cout << ans/2;
}

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