Submission #43881

#	Time	Username	Problem	Language	Result	Execution time	Memory
43881		cheater2k	The Forest of Fangorn (CEOI14_fangorn)	C++17	100 / 100	548 ms	1592 KiB

fangorn

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
const int C = 10005;

struct Point {
	int x; int y;
	Point(int x=0, int y=0): x(x), y(y) {}
	void operator -= (Point other) {
		x -= other.x; y -= other.y;
	}
	bool operator < (const Point &other) const {
		return x < other.x || (x == other.x && y < other.y);
	}
	bool operator == (const Point &other) const {
		return x == other.x && y == other.y;
	}
} gimli, camp[C], tree[N];
int n, w, h, ncamp;
Point lef[N], rig[N];

long long cross(Point O, Point A, Point B) {
	A -= O; B -= O;
	return 1LL * A.x * B.y - 1LL * A.y * B.x;
}

bool ccw(Point p, Point q) {
	return cross(Point(0, 0), p, q) >= 0;
}

bool cmp(Point p, Point q) {
	bool flag_p = Point(0, 0) < p;
	bool flag_q = Point(0, 0) < q;
	if (flag_p != flag_q) return flag_p > flag_q;
	return ccw(p, q);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> w >> h;
	cin >> gimli.x >> gimli.y;

	cin >> ncamp;
	for (int i = 1; i <= ncamp; ++i) cin >> camp[i].x >> camp[i].y;

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> tree[i].x >> tree[i].y;

	for (int i = 1; i <= n; ++i) {
		Point newG = gimli; newG -= tree[i];
		lef[i] = Point(0, 0);
		rig[i] = Point(0, 0);

		vector <Point> vec;
		vec.push_back(newG);
		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			Point symmetric = tree[j];
			symmetric -= tree[i];
			symmetric = Point(-symmetric.x, -symmetric.y);
			vec.push_back(symmetric);
		}

		sort(vec.begin(), vec.end(), cmp);
		int sz = vec.size();
		if (sz == 1) continue;

		// printf("\n");
		// for (auto &p : vec) printf("[%d %d]\n", p.x, p.y);

		for (int j = 0; j < sz; ++j) {
			if (vec[j] == newG) {
				lef[i] = vec[(j - 1 + sz) % sz];
				rig[i] = vec[(j + 1) % sz];
				// cerr << "lef " << lef[i].x << ' ' << lef[i].y << endl;
				// cerr << "rig " << rig[i].x << ' ' << rig[i].y << endl;
				break;
			}
		}
	}

	vector <int> vres;
	for (int i = 1; i <= ncamp; ++i) {
		bool ok = true;
		for (int j = 1; j <= n; ++j) {
			Point c = camp[i];
			c -= tree[j];
			if (lef[j] == Point(0, 0) || rig[j] == Point(0, 0)) continue;

			if (ccw(lef[j], rig[j])) {
				if (!(ccw(lef[j], c) && ccw(c, rig[j]))) ok = false;
			} else {
				if (ccw(rig[j], c) && ccw(c, lef[j])) ok = false;
			}
			if (!ok) break;
		}
		if (ok) vres.push_back(i);
	}

	printf("%d\n", vres.size());
	for (int &u : vres) printf("%d ", u);
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:102:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", vres.size());
                 ~~~~~~~~~~~^

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20