제출 #173482

#제출 시각아이디문제언어결과실행 시간메모리
173482jhwest2별자리 2 (JOI14_constellation2)C++14
55 / 100
9039 ms504 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...