Submission #447956

#	Time	Username	Problem	Language	Result	Execution time	Memory
447956		Jasiekstrz	Geometrija (COCI21_geometrija)	C++17	50 / 110	1082 ms	452 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];
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])
				continue;
			bool ok=true;
			for(int p=1;p<=n;p++)
			{
				if(p==i || p==j)
					continue;
				for(int q=p+1;q<=n;q++)
				{
					if(q!=i && q!=j && cross(tab[i],tab[j],tab[p],tab[q]))
					{
						//cerr<<tab[i].x<<","<<tab[i].y<<" "<<tab[j].x<<","<<tab[j].y<<" "
						//	<<tab[p].x<<","<<tab[p].y<<" "<<tab[q].x<<","<<tab[q].y<<"\n";
						ok=false;
						break;
					}
				}
				if(!ok)
					break;
			}
			if(ok)
				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: 0 / 60