Submission #20180

#	Time	Username	Problem	Language	Result	Execution time	Memory
20180		gs14004	별자리 2 (JOI14_constellation2)	C++14	55 / 100	9000 ms	1756 KiB

constellation2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
 
struct pnt{
	int x, y, c;
}a[3005];

int n;

lint ccw(pnt a, pnt b, pnt c){
	int dx1 = b.x - a.x;
	int dy1 = b.y - a.y;
	int dx2 = c.x - a.x;
	int dy2 = c.y - a.y;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i].x >> a[i].y >> a[i].c;
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i == j) continue;
			int cl[3] = {}, cr[3] = {}; // l -> i, r -> j
			for(int k=0; k<n; k++){
				if(i == k || j == k) continue;
				if(ccw(a[i], a[j], a[k]) > 0) cl[a[k].c]++;
				else cr[a[k].c]++;
			}
			lint tret = 1;
			for(int k=0; k<3; k++){
				if(a[i].c != k) tret *= cl[k];
				if(a[j].c != k) tret *= cr[k];
			}
			ret += tret;
		}
	}
	cout << ret / 2;
}

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