Cod sursa(job #896847)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 27 februarie 2013 17:35:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef struct{double x,y;}PUNCT;
PUNCT pct[120001];
int st[120001];
void schimba(PUNCT &a, PUNCT &b)
{
	PUNCT aux;
	aux=a;
	a=b;
	b=aux;
}
double crprod(PUNCT a,PUNCT b,PUNCT c)
{
	return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
bool comp(PUNCT a, PUNCT b)
{
	if(crprod(pct[1],a,b)<0)
		return 1;
	return 0;
}
int main()
{
	int n,i,lst;
	ifstream f("infasuratoare.in");
	f>>n;
	for(i=1;i<=n;i++)
		f>>pct[i].x>>pct[i].y;
	f.close();
	for(i=2;i<=n;i++)
	{
		if(pct[i].x<pct[1].x)
			schimba(pct[i],pct[1]);
		else
			if((pct[i].x==pct[1].x)&&(pct[i].y<pct[1].y))
				schimba(pct[i],pct[1]);
	}
	sort(pct+2,pct+1+n,comp);
	st[1]=1;
	st[2]=2;
	lst=2;
	for(i=3;i<=n;i++)
	{
		while((lst>=2)&&(crprod(pct[st[lst-1]],pct[st[lst]],pct[i])>=0))
			lst--;
		lst++;
		st[lst]=i;
	}
	while((lst>=2)&&(crprod(pct[st[lst-1]],pct[st[lst]],pct[1])>=0))
		lst--;
	ofstream g("infasuratoare.out");
	g<<fixed;
	g<<lst<<'\n';
	for(i=lst;i>0;i--)
		g<<setprecision(12)<<pct[st[i]].x<<" "<<pct[st[i]].y<<"\n";
	g.close();
	return 0;
}