Submission #110577

#	Time	Username	Problem	Language	Result	Execution time	Memory
110577		Mahdi_Jfri	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	2066 ms	896 KiB

fangorn

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

#define ll long long
#define pb push_back
#define ld long double
typedef complex<ld> point;

const int maxn = 1e4 + 20;
const ld pi = acos(-1);

point p[maxn] , a[maxn];

bool is[maxn];

point in()
{
	int x , y;
	cin >> x >> y;

	return point(x , y);
}

ld angle(point x)
{
	ld tmp = arg(x);
	if(tmp < 0)
		tmp += 2 * pi;

	return tmp;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int h , w;
	cin >> h >> w;

	point s = in();

	int c;
	cin >> c;

	for(int i = 0; i < c; i++)
		a[i] = in();

	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
		p[i] = in();

	memset(is , 1 , sizeof is);
	for(int i = 0; i < n; i++)
	{
		vector<ld> tmp;
		
		ld mn = 1e18 , mx = -1e18;
		for(int j = 0; j < n; j++)
		{
			if(i == j)
				continue;
			ld tmp = angle((p[i] - p[j]) / (s - p[i]));
			mn = min(mn , tmp);
			mx = max(mx , tmp);
		}

		for(int j = 0; j < c; j++)
			if(is[j])
			{
				ld tmp = angle((a[j] - p[i]) / (s - p[i]));
				if(!(mx <= tmp || tmp <= mn))
					is[j] = 0;
			}
	}

	vector<int> ans;
	for(int i = 0; i < c; i++)
		if(is[i])
			ans.pb(i);

	cout << ans.size() << endl;
	for(auto x : ans)
		cout << x + 1 << " ";
	cout << endl;
}

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