oj.uz

Submission #110577

# Submission time Handle Problem Language Result Execution time Memory
110577 2019-05-11T08:32:28 Z Mahdi_Jfri The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 2066 ms 896 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 117 ms 504 KB Output is correct
5 Correct 27 ms 384 KB Output is correct
6 Correct 423 ms 472 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 504 KB Output is correct
2 Correct 2066 ms 760 KB Output is correct
3 Correct 467 ms 896 KB Output is correct
4 Correct 1462 ms 776 KB Output is correct