Submission #25946

#	Time	Username	Problem	Language	Result	Execution time	Memory
25946		kdh9949	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	996 ms	2704 KiB

fangorn

#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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20