Submission #447935

#	Time	Username	Problem	Language	Result	Execution time	Memory
447935		Jasiekstrz	Geometrija (COCI21_geometrija)	C++17	0 / 110	1 ms	204 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;
}
Point tab[N+10];
vector<int> hull;
bool onhull[N+10];
bool vis[N+10];
int sgn(long long x)
{
	return (x<0 ? -1:1);
}
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;
}
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)
				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})
		{
			if(!vis[j])
				ans++;
		}
		vis[i]=true;
	}
	cout<<ans+hull.size()<<"\n";
	return 0;
}

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