oj.uz

Submission #20180

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

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Correct 1 ms 1756 KB Output is correct
3 Correct 8 ms 1756 KB Output is correct
4 Correct 24 ms 1756 KB Output is correct
5 Correct 55 ms 1756 KB Output is correct
6 Correct 185 ms 1756 KB Output is correct
7 Correct 184 ms 1756 KB Output is correct
8 Correct 184 ms 1756 KB Output is correct
9 Correct 181 ms 1756 KB Output is correct
10 Correct 105 ms 1756 KB Output is correct
11 Correct 178 ms 1756 KB Output is correct
12 Correct 179 ms 1756 KB Output is correct

Subtask #3
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3673 ms 1756 KB Output is correct
2 Correct 5329 ms 1756 KB Output is correct
3 Correct 7394 ms 1756 KB Output is correct
4 Correct 7417 ms 1756 KB Output is correct
5 Execution timed out 9000 ms 1752 KB Program timed out
6 Halted 0 ms 0 KB -