Submission #464547

#	Time	Username	Problem	Language	Result	Execution time	Memory
464547		Jasiekstrz	Zvijezda (COCI19_zvijezda)	C++17	110 / 110	123 ms	9472 KiB

zvijezda

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
struct Point
{
	long long x,y;
};
int operator*(Point a,Point b)
{
	__int128 c=(__int128)a.x*b.y-(__int128)a.y*b.x;
	if(c==0)
		return 0;
	return (c<0 ? -1:1);
}
Point operator-(Point a,Point b)
{
	return {a.x-b.x,a.y-b.y};
}
bool under(Point p,Point a,Point b)
{
	return (b-a)*(p-a)>=0;
}
bool comp(Point p,Point a,Point b)
{
	return (a-p)*(b-p)>0;
}
Point tab[N+10];
int bs(Point p,int l,int r)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(comp(p,tab[mid],tab[mid+1]))
			r=mid;
		else
			l=mid+1;
	}
	return l;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,t;
	cin>>t;
	cin>>n;
	int mn=1,mx=1;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i].x>>tab[i].y;
		tab[n+i]=tab[i];
		if(tab[i].x<tab[mn].x)
			mn=i;
		if(tab[i].x>tab[mx].x)
			mx=i;
	}
	if(mn>mx)
		swap(mn,mx);
	pair<int,int> seg[2]={{mn,mx},{mx,n+mn}};
	int q;
	cin>>q;
	long long ans=0;
	while(q--)
	{
		long long a,b;
		cin>>a>>b;
		Point p={a^(ans*ans*ans*t),b^(ans*ans*ans*t)};
		int w[2];
		for(int i:{0,1})
			w[i]=bs(p,seg[i].fi,seg[i].se);
		int ww=(comp(p,tab[w[0]],tab[w[1]]) ? w[0]:w[1]);
		ww=(ww-1)%n+1;
		if(under(p,tab[ww+n/2],tab[ww+n/2+1]))
		{
			ans++;
			cout<<"DA\n";
		}
		else
			cout<<"NE\n";
	}
	return 0;
}

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