Submission #20181

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

constellation2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <assert.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++){
		int cl[3] = {}, cr[3] = {};
		vector<pnt> v;
		for(int j=0; j<n; j++){
			if(i != j) v.push_back(a[j]);
		}
		sort(v.begin(), v.end(), [&](const pnt &p, const pnt &q){
			return atan2(a[i].y - p.y, a[i].x - p.x) < atan2(a[i].y - q.y, a[i].x - q.x);
		});
		for(int i=0; i<n-1; i++){
			cr[v[i].c]++;
			v.push_back(v[i]);
		}
		int p = 0;
		for(int j=0; j<n-1; j++){
			while(p < n-1+j && ccw(a[i], v[j], v[p]) >= 0){
				cl[v[p].c]++;
				cr[v[p].c]--;
				p++;
			}
			cl[v[j].c]--;
			lint tret = 1;
			for(int k=0; k<3; k++){
				if(a[i].c != k) tret *= cl[k];
				if(v[j].c != k) tret *= cr[k];
			}
			ret += tret;
			cr[v[j].c]++;
		}
	}
	cout << ret / 2;
}

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