Submission #59300

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

fangorn

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

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

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() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> w >> h >> sx >> sy >> c;
	for(int i=0; i<c; ++i)
		cin >> cx[i] >> cy[i];
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> tx[i] >> ty[i];
	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;
		}
//		cout << (double)pa.fi/pa.se << " " << (double)pb.fi/pb.se << " " << (double)pc.fi/pc.se << endl;
		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;
//				cout << cx[j] << " " << tx[i
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
//				if(j==1)
//				cout << (double)pd.fi/pd.se << endl;
				a1[j]=fc(pb, pd)&&fc(pd, pc);
			}
		}
	}
	for(int i=0; i<c; ++i)
		m+=a1[i];
	cout << m << "\n";
	for(int i=0; i<c; ++i)
		if(a1[i])
			cout << i+1 << " ";
}

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