Submission #49527

#	Time	Username	Problem	Language	Result	Execution time	Memory
49527		minkank	별자리 2 (JOI14_constellation2)	C++17	100 / 100	3085 ms	2076 KiB

constellation2

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45