oj.uz

Submission #100962

# Submission time Handle Problem Language Result Execution time Memory
100962 2019-03-15T13:28:42 Z square1001 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 283 ms 552 KB 
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 2 ms 304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 12 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 53 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 384 KB Output is correct
2 Correct 217 ms 552 KB Output is correct
3 Correct 283 ms 512 KB Output is correct
4 Correct 174 ms 512 KB Output is correct