oj.uz

Submission #43881

# Submission time Handle Problem Language Result Execution time Memory
43881 2018-03-27T01:36:21 Z cheater2k The Forest of Fangorn (CEOI14_fangorn) C++17
100 / 100
 548 ms 1592 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 660 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 868 KB Output is correct
5 Correct 3 ms 868 KB Output is correct
6 Correct 4 ms 868 KB Output is correct
7 Correct 2 ms 868 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 2 ms 868 KB Output is correct
10 Correct 5 ms 876 KB Output is correct
11 Correct 5 ms 880 KB Output is correct
12 Correct 5 ms 888 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 928 KB Output is correct
2 Correct 2 ms 1060 KB Output is correct
3 Correct 2 ms 1060 KB Output is correct
4 Correct 113 ms 1084 KB Output is correct
5 Correct 30 ms 1084 KB Output is correct
6 Correct 485 ms 1124 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 1172 KB Output is correct
2 Correct 548 ms 1328 KB Output is correct
3 Correct 487 ms 1564 KB Output is correct
4 Correct 308 ms 1592 KB Output is correct