Submission #1236217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236217		kaiboy	The Forest of Fangorn (CEOI14_fangorn)	C++20	100 / 100	114 ms	580 KiB

fangorn

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2000;
const int K = 10000;

int xx[N], yy[N], ii[N], xx_[K], yy_[K];
bool bad[K];

long long cross(int x0, int y0, int x1, int y1) {
	return (long long) x0 * y1 - (long long) x1 * y0;
}

long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
	return cross(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int x_, y_, xg, yg, k; cin >> x_ >> y_ >> xg >> yg >> k;
	for (int h = 0; h < k; h++)
		cin >> xx_[h] >> yy_[h];
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> xx[i] >> yy[i];
	for (int i_ = 0; i_ < n; i_++) {
		int xo = xx[i_], yo = yy[i_];
		int il = -1, ir = -1;
		for (int i = 0; i < n; i++)
			if (i != i_) {
				int x = xx[i], y = yy[i];
				if (cross(xo, yo, xg, yg, x, y) > 0) {
					if (il == -1 || cross(xo, yo, xx[il], yy[il], x, y) < 0)
						il = i;
					if (ir == -1 || cross(xo, yo, xx[ir], yy[ir], x, y) > 0)
						ir = i;
				}
			}
		int jl = -1, jr = -1;
		for (int j = 0; j < n; j++)
			if (j != i_) {
				int x = xx[j], y = yy[j];
				if (cross(xo, yo, xg, yg, x, y) < 0) {
					if (jl == -1 || cross(xo, yo, xx[jl], yy[jl], x, y) > 0)
						jl = j;
					if (jr == -1 || cross(xo, yo, xx[jr], yy[jr], x, y) < 0)
						jr = j;
				}
			}
		if (il == -1) {
			int xl = xx[jl], yl = yy[jl], xr = xx[jr], yr = yy[jr];
			for (int h = 0; h < k; h++) {
				int x = xx_[h], y = yy_[h];
				if (cross(xl, yl, xo, yo, x, y) < 0 && cross(xr, yr, xo, yo, x, y) > 0)
					bad[h] = true;
			}
		} else if (jl == -1) {
			int xl = xx[il], yl = yy[il], xr = xx[ir], yr = yy[ir];
			for (int h = 0; h < k; h++) {
				int x = xx_[h], y = yy_[h];
				if (cross(xl, yl, xo, yo, x, y) > 0 && cross(xr, yr, xo, yo, x, y) < 0)
					bad[h] = true;
			}
		} else {
			int xi = xx[ir], yi = yy[ir], xj = xx[jr], yj = yy[jr];
			for (int h = 0; h < k; h++) {
				int x = xx_[h], y = yy_[h];
				if (cross(xo, yo, xg, yg, x, y) > 0) {
					if (cross(xj, yj, xo, yo, x, y) > 0)
						bad[h] = true;
				} else {
					if (cross(xi, yi, xo, yo, x, y) < 0)
						bad[h] = true;
				}
			}
		}
	}
	int cnt = 0;
	for (int h = 0; h < k; h++)
		if (!bad[h])
			cnt++;
	cout << cnt << '\n';
	for (int h = 0; h < k; h++)
		if (!bad[h])
			cout << h + 1 << ' ';
	cout << '\n';
	return 0;
}

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