oj.uz

Submission #49527

# Submission time Handle Problem Language Result Execution time Memory
49527 2018-05-30T07:47:20 Z minkank 별자리 2 (JOI14_constellation2) C++17
100 / 100
 3085 ms 2076 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 3005;
 
struct Point {
	int x, y, type;
	bool operator < (Point u) {
		return angle() < u.angle();
	}
	bool operator != (Point u) {
		return (x != u.x) || (y != u.y);
	}
	double angle() {
		double tmp = atan2(y, x);
		if(tmp < 0) tmp += acos(-1) * 2;
		return tmp;
	}
	Point inv() {
		return {-x, -y, 0};
	}
};
 
bool sortCmp(Point x, Point y) {
	if(x.y >= 0 && y.y < 0) return 1;
	if(x.y < 0 && y.y >= 0) return 0;
	if(x.y == 0 && y.y == 0) return x.x > y.x;
	return 1LL * x.x * y.y - 1LL * x.y * y.x > 0;
}
 
int n, cnt[4], dem[4];
Point a[N];
 
int main() {
	cin >> n;
	long long ans = 0;
	for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].type;
	for(int root = 1; root <= n; ++root) {
		vector<Point> p;
		dem[0] = dem[1] = dem[2] = cnt[0] = cnt[1] = cnt[2] = 0;
		for(int i = 1; i <= n; ++i) if(i != root) {
			Point tmp = a[i];
			tmp.x -= a[root].x; tmp.y -= a[root].y;
			p.push_back(tmp);
			p.push_back(tmp.inv());
			p[p.size() - 1].type = 3;
			dem[tmp.type]++;
		}
		sort(p.begin(), p.end(), sortCmp);
		int j = 0;
		for(int i = 0; i < p.size(); ++i) {
			while(p[j] != p[i].inv()) cnt[p[j].type]++, dem[p[j].type]--, j++, j %= (int)p.size();
			while(!(p[j] != p[i].inv())) cnt[p[j].type]++, dem[p[j].type]--, j++, j %= (int)p.size();
			long long sum1 = 1, sum2 = 1; int t1 = a[root].type; int t2 = p[i].type;
			if(p[i].type == 3) continue;
			for(int j = 0; j <= 2; ++j) if(j != t1) sum1 *= dem[j];
			for(int j = 0; j <= 2; ++j) if(j != t2)	sum2 *= cnt[j];
			ans += sum1 * sum2;
			cnt[p[i].type]--; dem[p[i].type]++;
		}
	}
	cout << ans / 2 << '\n';
}

Compilation message

constellation2.cpp: In function 'int main()':
constellation2.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < p.size(); ++i) {
                  ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 840 KB Output is correct
11 Correct 2 ms 840 KB Output is correct
12 Correct 3 ms 840 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 840 KB Output is correct
2 Correct 3 ms 840 KB Output is correct
3 Correct 5 ms 872 KB Output is correct
4 Correct 10 ms 872 KB Output is correct
5 Correct 16 ms 872 KB Output is correct
6 Correct 26 ms 876 KB Output is correct
7 Correct 26 ms 880 KB Output is correct
8 Correct 24 ms 880 KB Output is correct
9 Correct 31 ms 980 KB Output is correct
10 Correct 17 ms 980 KB Output is correct
11 Correct 26 ms 980 KB Output is correct
12 Correct 23 ms 980 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 1036 KB Output is correct
2 Correct 271 ms 1044 KB Output is correct
3 Correct 322 ms 1132 KB Output is correct
4 Correct 279 ms 1132 KB Output is correct
5 Correct 654 ms 1164 KB Output is correct
6 Correct 1174 ms 1184 KB Output is correct
7 Correct 2017 ms 1524 KB Output is correct
8 Correct 2777 ms 1700 KB Output is correct
9 Correct 2735 ms 1704 KB Output is correct
10 Correct 2789 ms 1744 KB Output is correct
11 Correct 3085 ms 1744 KB Output is correct
12 Correct 2876 ms 1820 KB Output is correct
13 Correct 2841 ms 1972 KB Output is correct
14 Correct 2920 ms 2036 KB Output is correct
15 Correct 2951 ms 2076 KB Output is correct
16 Correct 2866 ms 2076 KB Output is correct