Cod sursa(job #3256772)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 16 noiembrie 2024 09:44:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
	double x,y;
	bool operator == (point b)
	{
		return x==b.x&&y==b.y;
	}
} v[120005],start;
int n;
double aria(point a,point b,point c)
{
	a.x-=c.x;
	b.x-=c.x;
	a.y-=c.y;
	b.y-=c.y;
	return a.x*b.y-a.y*b.x;
}
bool comp(point a,point b)
{
	if(a==start)
		return 1;
	if(b==start)
		return 0;
	double val=aria(start,a,b);
	if(val==0)
		return a.x<b.x;
	return val>0;
}
int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	start={2e9,2e9};
	fin>>n;
	for(int i=1;i<=n;i++)
	{
		fin>>v[i].x>>v[i].y;
		if(v[i].x<start.x)
			start=v[i];
		else if(v[i].x==start.x)
			start.y=min(start.y,v[i].y);
	}
	sort(v+1,v+n+1,comp);
	vector<point> sol;
	for(int i=1;i<=n;i++)
	{
		point p=v[i];
		while(sol.size()>=2)
		{
			int lg=sol.size();
			point a=sol[lg-2];
			point b=sol[lg-1];
			if(aria(a,b,p)<0)
				sol.pop_back();
			else
				break;
		}
		sol.push_back(p);
	}
	fout<<sol.size()<<'\n';
	for(point p:sol)
		fout<<fixed<<setprecision(12)<<p.x<<' '<<p.y<<'\n';
	return 0;
}