oj.uz

Submission #20181

# Submission time Handle Problem Language Result Execution time Memory
20181 2016-03-01T14:39:42 Z gs14004 별자리 2 (JOI14_constellation2) C++14
55 / 100
 9000 ms 2180 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1992 KB Output is correct
2 Correct 0 ms 1992 KB Output is correct
3 Correct 0 ms 1992 KB Output is correct
4 Correct 0 ms 1992 KB Output is correct
5 Correct 0 ms 1992 KB Output is correct
6 Correct 0 ms 1992 KB Output is correct
7 Correct 0 ms 1992 KB Output is correct
8 Correct 0 ms 1992 KB Output is correct
9 Correct 0 ms 1992 KB Output is correct
10 Correct 0 ms 1992 KB Output is correct
11 Correct 1 ms 1992 KB Output is correct
12 Correct 0 ms 1992 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1992 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 11 ms 1992 KB Output is correct
4 Correct 27 ms 1992 KB Output is correct
5 Correct 50 ms 1992 KB Output is correct
6 Correct 120 ms 1992 KB Output is correct
7 Correct 115 ms 1992 KB Output is correct
8 Correct 118 ms 1992 KB Output is correct
9 Correct 117 ms 1992 KB Output is correct
10 Correct 82 ms 1992 KB Output is correct
11 Correct 117 ms 1992 KB Output is correct
12 Correct 90 ms 1992 KB Output is correct

Subtask #3
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 954 ms 1992 KB Output is correct
2 Correct 1226 ms 1992 KB Output is correct
3 Correct 1538 ms 1992 KB Output is correct
4 Correct 1563 ms 1992 KB Output is correct
5 Correct 3644 ms 1992 KB Output is correct
6 Correct 6862 ms 1992 KB Output is correct
7 Execution timed out 9000 ms 2180 KB Program timed out
8 Halted 0 ms 0 KB -