oj.uz

Submission #25946

# Submission time Handle Problem Language Result Execution time Memory
25946 2017-06-25T07:46:37 Z kdh9949 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 996 ms 2704 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pos{ int x, y; };

int w, h, n, c, ans, chk[10010];
Pos ip, cp[10010], a[2010], ca[2010];
set<int> ss;

int ccw(Pos a, Pos b, Pos c){
	ll t = 1LL * (b.x - a.x) * (c.y - b.y) - 1LL * (c.x - b.x) * (b.y - a.y);
	return t > 0 ? 1 : t < 0 ? -1 : 0;
}

int main(){
	scanf("%d%d%d%d%d", &w, &h, &ip.x, &ip.y, &c);
	for(int i = 1; i <= c; i++){
		scanf("%d%d", &cp[i].x, &cp[i].y);
		ss.insert(i);
	}
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d", &a[i].x, &a[i].y);
	}
	ans = c;
	for(int i = 1; i <= n; i++){
		swap(a[1], a[i]);
		for(int j = 2; j <= n; j++) ca[j - 1] = {2 * a[1].x - a[j].x, 2 * a[1].y - a[j].y};
		auto cmp = [](Pos p, Pos q){
			int px = (p.y < a[1].y || (p.y == a[1].y && p.x < a[1].x));
			int qx = (q.y < a[1].y || (q.y == a[1].y && q.x < a[1].x));
			if(px != qx) return px < qx;
			return ccw(a[1], p, q) > 0;
		};
		sort(ca + 1, ca + n, cmp);
		int t = (int)(lower_bound(ca + 1, ca + n, ip, cmp) - ca);
		if(t == n) t = 1;
		for(int i = 1; i <= c; i++){
			if(chk[i]) continue;
			int u = (int)(lower_bound(ca + 1, ca + n, cp[i], cmp) - ca);
			if(u == n) u = 1;
			if(u != t){
				chk[i] = 1;
				ans--;
			}
		}
		swap(a[1], a[i]);
	}
	printf("%d\n", ans);
	for(int i = 1; i <= c; i++) if(!chk[i]) printf("%d ", i);
	return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:17:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &w, &h, &ip.x, &ip.y, &c);
                                               ^
fangorn.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &cp[i].x, &cp[i].y);
                                    ^
fangorn.cpp:22:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
fangorn.cpp:24:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].x, &a[i].y);
                                  ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2176 KB Output is correct
2 Correct 0 ms 2176 KB Output is correct
3 Correct 0 ms 2176 KB Output is correct
4 Correct 96 ms 2176 KB Output is correct
5 Correct 19 ms 2176 KB Output is correct
6 Correct 436 ms 2176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 2308 KB Output is correct
2 Correct 996 ms 2572 KB Output is correct
3 Correct 419 ms 2572 KB Output is correct
4 Correct 756 ms 2704 KB Output is correct