Cod sursa(job #729223)

Utilizator paulbotabota paul paulbota Data 29 martie 2012 13:18:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<fstream>
#include<vector>
#include<math.h>
#include<cstdio>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define maxn 120010
#define inF "infasuratoare.in"
#define outF "infasuratoare.out"

using namespace std;

ifstream in(inF);

vector<pair<double,double> >vect;
int N,origine,v[maxn],coada[maxn];

bool cmp(int x,int y)
{
	return (vect[x].first-vect[origine].first)*(vect[y].second-vect[origine].second)<(vect[y].first-vect[origine].first)*(vect[x].second-vect[origine].second);
}

long double unghi(int x, int y, int z)
{
	return (long double)(vect[x].first*vect[y].second+vect[y].first*vect[z].second+vect[z].first*vect[x].second)-(long double)(vect[x].second*vect[y].first+vect[y].second*vect[z].first+vect[z].second*vect[x].first);
}

void read()
{
	in>>N;
	for(int i=0;i<N;i++)
	{
		double x,y;
		in>>x>>y;
		vect.pb(mp(x,y));
		if(x<vect[origine].first || (x==vect[origine].first && y<vect[origine].second)) origine=i;
	}
}

int main()
{
	int i;
	read();
	for(i=1;i<=N;i++)
	{
		if(i==origine) continue;
		v[++v[0]]=i;
	}
	sort(v+1,v+v[0]+1,cmp);
	coada[++coada[0]]=origine;
	for(i=1;i<=N;i++)
	{
		if(v[i]==origine) continue;
		while(v[0]>=2 && unghi(coada[coada[0]-1],coada[coada[0]],v[i])>0) --coada[0];
		coada[++coada[0]]=v[i];
	}
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",coada[0]);
	reverse(coada+1,coada+coada[0]+1);
	for(i=1;i<=coada[0];i++)
	{
		printf("%lf %lf\n",vect[coada[i]].first,vect[coada[i]].second);
	}
	return 0;
}