Submission #254117

#	Time	Username	Problem	Language	Result	Execution time	Memory
254117		MrRobot_28	Zvijezda (COCI19_zvijezda)	C++17	110 / 110	153 ms	8056 KiB

zvijezda

#include<bits/stdc++.h>
 
using namespace std;
#define int long long
vector <pair <int, int> > pol;
int n;
bool crossproduct(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
	return (double)b.first * (c.second - a.second) +
         (double)c.first * (a.second - b.second) +
         (double)a.first * (b.second - c.second) >= 0;
}
int check(pair <int, int> a, int l, int r)
{
	int al = l, ar = r + 1;
	while(ar - al > 1)
	{
		int midd = (ar + al) / 2;
		if(crossproduct(a, pol[midd], pol[(midd + 1) % n]) == crossproduct(a, pol[l], pol[(l + 1) % n]))
		{
			al = midd;
		}
		else
		{
			ar = midd;
		}
	}
	if(crossproduct(a, pol[l], pol[(l + 1) % n]))
	{
		return al - l + 1;
	}
	else
	{
		return (r - l + 1) - (al - l + 1);
	}
}
bool solve(int x, int y)
{
	bool a = crossproduct({x, y}, pol[0], pol[1 % n]);
	bool b = crossproduct({x, y}, pol[n / 2], pol[(n / 2 + 1) % n]);
	if(a == b)
	{
		return a;
	}
	return check({x, y}, 0, n / 2 - 1) + check({x, y}, n / 2, n - 1) > n / 2;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t >> n;
	pol.resize(n);
	for(int i = 0; i < n; i++)
	{
		cin >> pol[i].first >> pol[i].second;
	}
	int q;
	cin >> q;
	int preans = 0;
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		x ^= t * preans * preans * preans;
		y ^= t * preans * preans * preans;
		int ans = solve(x, y);
		preans += ans;
		if(ans)
		{
			cout << "DA\n";
		}
		else
		{
			cout << "NE\n";
		}
	}
	return 0;
}

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