Submission #59762

#	Time	Username	Problem	Language	Result	Execution time	Memory
59762		tmwilliamlin168	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	178 ms	1400 KiB

fangorn

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while(true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, c=0;
	if(!x) {
		putchar_unlocked('0');
		return;
	}
	while(!(rev%10)) {
		++c;
		rev/=10;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(c--)
		putchar_unlocked('0');
}
 
const int mxC=1e4, mxN=2e3;
int c, n, m;
ll w, h, sx, sy, cx[mxC], cy[mxC], tx[mxN], ty[mxN];
bool a1[mxC];
 
inline bool fc(pll a, pll b) {
	return a.fi*b.se<b.fi*a.se;
}
 
inline pll af(ll dx, ll dy) {
	return dy<0?pll(dx-abs(dx)+dy, abs(dx)-dy):pll(abs(dx)-dx+dy, abs(dx)+dy);
}
 
int main() {
	w=in(), h=in(), sx=in(), sy=in(), c=in();
	for(int i=0; i<c; ++i) {
		cx[i]=in();
		cy[i]=in();
	}
	n=in();
	for(int i=0; i<n; ++i) {
		tx[i]=in();
		ty[i]=in();
	}
	memset(a1, 1, c);
	for(int i=0; i<n; ++i) {
		pll pa=af(sx-tx[i], sy-ty[i]), pb={-3, 1}, pc={3, 1};
		for(int j=0; j<n; ++j) {
			if(j==i)
				continue;
			pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
			if(fc(pa, pd)&&fc(pd, pc))
				pc=pd;
			else if(fc(pd, pa)&&fc(pb, pd))
				pb=pd;
		}
		if(pb==pll(-3, 1)||pc==pll(3, 1)) {
			if(pb.fi==-3) {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pb, pd))
						pb=pd;
				}
			} else {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pd, pc))
						pc=pd;
				}
			}
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
				a1[j]=fc(pb, pd)||fc(pd, pc);
			}
		} else {
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
				a1[j]=fc(pb, pd)&&fc(pd, pc);
			}
		}
	}
	for(int i=0; i<c; ++i)
		m+=a1[i];
	out(m);
	putchar_unlocked('\n');
	for(int i=0; i<c; ++i) {
		if(a1[i]) {
			out(i+1);
			putchar_unlocked(' ');
		}
	}
}

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