Submission #100962

#	Time	Username	Problem	Language	Result	Execution time	Memory
100962		square1001	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	283 ms	552 KiB

fangorn

class point2d {
public:
	long long x, y;
	point2d() : x(0), y(0) {};
	point2d(long long x_, long long y_) : x(x_), y(y_) {};
	point2d& operator+=(const point2d& p) { x += p.x; y += p.y; return *this; }
	point2d& operator-=(const point2d& p) { x -= p.x; y -= p.y; return *this; }
	point2d operator+(const point2d& p) const { return point2d(*this) += p; }
	point2d operator-(const point2d& p) const { return point2d(*this) -= p; }
	int shougen() {
		if (y == 0) return x > 0 ? 0 : 2;
		return y > 0 ? 1 : 3;
	}
	bool operator<(point2d& p) {
		int s = shougen(), sp = p.shougen();
		if (s != sp) return s < sp;
		return x * p.y - y * p.x > 0;
	}
	bool operator>(point2d& p) {
		int s = shougen(), sp = p.shougen();
		if (s != sp) return s > sp;
		return x * p.y - y * p.x < 0;
	}
};

#include <vector>
#include <iostream>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int W, H, C, N; point2d G;
	cin >> W >> H >> G.x >> G.y;
	cin >> C;
	vector<point2d> CP(C);
	for (int i = 0; i < C; ++i) {
		cin >> CP[i].x >> CP[i].y;
	}
	cin >> N;
	vector<point2d> TP(N);
	for (int i = 0; i < N; ++i) {
		cin >> TP[i].x >> TP[i].y;
	}
	vector<bool> ans(C, true);
	for (int i = 0; i < N; ++i) {
		point2d lp, rp;
		bool lfound = false, rfound = false;
		point2d dg = G - TP[i];
		for (int j = 0; j < N; ++j) {
			if (i == j) continue;
			point2d d = TP[i] - TP[j];
			if (d < dg) {
				if (!lfound || lp < d) {
					lfound = true;
					lp = d;
				}
			}
			else {
				if (!rfound || rp > d) {
					rfound = true;
					rp = d;
				}
			}
		}
		if (!lfound) {
			bool flag = false;
			for (int j = 0; j < N; ++j) {
				if (i == j) continue;
				point2d d = TP[i] - TP[j];
				if (!flag || d > lp) {
					flag = true;
					lp = d;
				}
			}
		}
		if (!rfound) {
			bool flag = false;
			for (int j = 0; j < N; ++j) {
				if (i == j) continue;
				point2d d = TP[i] - TP[j];
				if (!flag || d < rp) {
					flag = true;
					rp = d;
				}
			}
		}
		for (int j = 0; j < C; ++j) {
			point2d d = CP[j] - TP[i];
			if (lfound && rfound && !(lp < d && d < rp)) ans[j] = false;
			if (((lfound && !rfound) || (!lfound && rfound)) && !(lp < d || d < rp)) ans[j] = false;
		}
	}
	int cnt = 0;
	for (int i = 0; i < C; ++i) {
		if (ans[i]) ++cnt;
	}
	cout << cnt << '\n';
	for (int i = 0; i < C; ++i) {
		if (ans[i]) {
			cout << i + 1 << (--cnt > 0 ? ' ' : '\n');
		}
	}
	return 0;
}

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