Submission #447966

#	Time	Username	Problem	Language	Result	Execution time	Memory
447966		Jasiekstrz	Geometrija (COCI21_geometrija)	C++17	110 / 110	175 ms	564 KiB

geometrija

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
struct Point
{
	long long x,y;
};
Point operator-(Point a,Point b)
{
	return {a.x-b.x,a.y-b.y};
}
long long operator*(Point a,Point b)
{
	return a.x*b.y-a.y*b.x;
}
int sgn(long long x)
{
	return (x<0 ? -1:1);
}
int ilo(Point a,Point b,Point c)
{
	return sgn((a-c)*(b-c));
}
bool cross(Point a,Point b,Point c,Point d)
{
	return (ilo(c,b,a)!=ilo(d,b,a) && ilo(a,d,c)!=ilo(b,d,c));
}
bool inside(Point p,Point a,Point b,Point c)
{
	int val=sgn((p-a)*(b-a));
	if(sgn((p-b)*(c-b))==val && sgn((p-c)*(a-c))==val)
		return true;
	return false;
}
Point tab[N+10];
vector<int> hull;
bool onhull[N+10];
bool vis[N+10];
bool cross_all(Point a,Point b,int n)
{
	vector<Point> t[2];
	for(int i=1;i<=n;i++)
	{
		long long tmp=(tab[i]-b)*(a-b);
		if(tmp>0)
			t[1].push_back(tab[i]);
		else if(tmp<0)
			t[0].push_back(tab[i]);
	}
	vector<Point> sa=t[0],sb=t[0];
	sort(sa.begin(),sa.end(),[&a](Point p,Point q){ return (p-a)*(q-a)<0; });
	sort(sb.begin(),sb.end(),[&b](Point p,Point q){ return (p-b)*(q-b)<0; });
	for(auto v:t[1])
	{
		int cnt=t[0].size();

		int bg=0,en=sb.size();
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if((b-v)*(sb[mid-1]-b)>0)
				bg=mid;
			else
				en=mid-1;
		}
		cnt-=bg;

		bg=0,en=sa.size();
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if((a-v)*(sa[sa.size()-mid]-a)<0)
				bg=mid;
			else
				en=mid-1;
		}
		cnt-=bg;

		if(cnt>0)
			return true;
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>tab[i].x>>tab[i].y;
	sort(tab+1,tab+n+1,[](Point a,Point b){ return a.x<b.x; });

	auto pop_bad=[](int x)
	{
		while(hull.size()>1 && 
				(tab[x]-tab[hull[hull.size()-2]])*(tab[hull.back()]-tab[hull[hull.size()-2]])<0)
			hull.pop_back();
		hull.push_back(x);
		return;
	};
	for(int i=1;i<=n;i++)
		pop_bad(i);
	for(int i=n-1;i>=1;i--)
		pop_bad(i);
	hull.pop_back();
	for(auto v:hull)
		onhull[v]=true;
	//for(auto v:hull)
	//	cerr<<tab[v].x<<" "<<tab[v].y<<"\n";

	for(int i=1;i<=n;i++)
	{
		if(onhull[i])
			continue;
		int a=1,b,c;
		for(b=1,c=2;sgn((tab[hull[b]]-tab[a])*(tab[i]-tab[a]))==
				sgn((tab[hull[c]]-tab[a])*(tab[i]-tab[a]));b++,c++);
		b=hull[b];
		c=hull[c];
		for(int j=1;j<=n;j++)
		{
			if(j==i || j==a || j==b || j==c || !inside(tab[j],tab[a],tab[b],tab[c]))
				continue;
			if(inside(tab[i],tab[a],tab[b],tab[j]))
				c=j;
			else if(inside(tab[i],tab[a],tab[j],tab[c]))
				b=j;
			else if(inside(tab[i],tab[j],tab[b],tab[c]))
				a=j;
		}
		for(int j:{a,b,c})
		{
			//cerr<<tab[i].x<<","<<tab[i].y<<" "<<tab[j].x<<","<<tab[j].y<<"\n";
			if(!vis[j] && !cross_all(tab[i],tab[j],n))
				ans++;
		}
		vis[i]=true;
		//cerr<<tab[i].x<<" "<<tab[i].y<<" "<<ans<<"\n";
	}
	cout<<ans+hull.size()<<"\n";
	return 0;
}

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