Submission #131853

#	Time	Username	Problem	Language	Result	Execution time	Memory
131853		bogdan10bos	The Forest of Fangorn (CEOI14_fangorn)	C++14	80 / 100	2677 ms	32888 KiB

fangorn

/// ASE sucks
/// (Trappere nu esti hard, da)
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef double mydouble;

const int CMAX = 10005;
const int NMAX = 2005;

int H, W, X, Y, C, N;
int cx[CMAX], cy[CMAX];
int px[NMAX], py[NMAX], part[NMAX];
vector<mydouble> drp[NMAX];

int findPart(int id, mydouble val)
{
	int ans = 0;
	int p = 0, u = (int)drp[id].size() - 1;
	while(p <= u)
	{
		int mij = p + (u - p) / 2;
		if(drp[id][mij] >= val)
		{
			ans = mij;
			u = mij - 1;
		}
		else
			p = mij + 1;
	}
	return ans;
}

int main()
{
	scanf("%d%d", &H, &W);
	scanf("%d%d", &X, &Y);
	scanf("%d", &C);
	for(int i = 1; i <= C; i++)
		scanf("%d%d", &cx[i], &cy[i]);
	scanf("%d", &N);
	for(int i = 1; i <= N; i++)
		scanf("%d%d", &px[i], &py[i]);
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
			if(i != j)
				drp[i].push_back(atan2(px[i] - px[j], py[i] - py[j]));
		sort(drp[i].begin(), drp[i].end());
	}

	for(int i = 1; i <= N; i++)
		part[i] = findPart(i, atan2(X - px[i], Y - py[i]));

	vector<int> ord;
	for(int i = 1; i <= N; i++)	ord.push_back(i);
	mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
	shuffle(ord.begin(), ord.end(), g);

	while( (int)ord.size() > 1100 )	ord.pop_back();

	vector<int> sol;
	for(int i = 1; i <= C; i++)
	{
		bool ok = true;
		for(auto &id: ord)
		{
			int prt = findPart(id, atan2(cx[i] - px[id], cy[i] - py[id]));
			if(prt != part[id])
			{
				ok = false;
				break;
			}
		}
		if(ok)	sol.push_back(i);
	}

	sort(sol.begin(), sol.end());
	printf("%d\n", (int)sol.size());
	for(auto x: sol)	printf("%d ", x);
	return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
  ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &X, &Y);
  ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
fangorn.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &cx[i], &cy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
fangorn.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &px[i], &py[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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