Cod sursa(job #2700827)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 28 ianuarie 2021 23:24:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int St[120005];
bool viz[120005];

struct node
{
	double first,second;
};

node p[120005];

bool ok(node &a,node &b)
{
	if(a.first==b.first)
		return a.second<b.second;
	return a.first<b.first;
}

double det(node &a ,node &b,node &c)
{
	return(b.first-a.first)*(c.second-b.second)-(b.second-a.second)*(c.first-b.first);
}
void solve(int &n,int &h)
{
	sort(p+1,p+n+1,ok);
	St[1]=1;
	St[2]=2;
	viz[2]=1;
	int p=1;
	for(int i=3;i>=1;i+=p)
	{
		if(viz[i]!=0) continue;
		while(h>=2 && det(p[St[h-1]],p[St[h]],p[i])<0)
			viz[St[h--]]=0;
		St[++h]=i;
		viz[i]=1;
		if(i==n)
			p-=1;
	}
	h--;
}
int main()
{
	int n,h=2;
	in>>n;
	for(int i=1;i<=n;i++)
		in>>p[i].first>>p[i].second;
	solve(n,h);
	out<<h<<"\n";
	out<<fixed<<setprecision(6);
	for(int i=1;i<=h;i++)
		out<<p[St[i]].x<<" "<<p[St[i]].y<<"\n";
	return 0;
}