Cod sursa(job #753657)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 30 mai 2012 11:04:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,l1,l2;
typedef pair<double,double> pdd;
pdd a[120100];

struct cmp
{
	inline bool operator()(const pdd &a,const pdd &b)const
	{
		if(a.first==b.first)
		{
			return a.second<b.second;
		}
		return a.first<b.first;
	}
};

inline int semiplan(pdd a,pdd b,pdd c)
{
	if((a.first*b.second*1)+(b.first*c.second*1)+(c.first*a.second*1)>(1*b.second*c.first)+(1*c.second*a.first)+(1*a.second*b.first))
		return 1;
	return -1;
}

int stv[120100],ok[120100];

inline void make()
{
	int lf=0,pas=1,i;
	stv[++stv[0]]=1;stv[++stv[0]]=2;
	i=3;
	
	while(i>1)
	{
		while(ok[i])
		{
			i+=pas;
			if(i==n)
			{
				pas=-1;
			}
		}
		
		while(semiplan(a[stv[stv[0]-1]],a[stv[stv[0]]],a[i])==-1 && stv[0]>=2)
		{
			ok[stv[stv[0]--]]=0;
		}
		
		ok[i]=1;
		stv[++stv[0]]=i;
	}
	
	printf("%d\n",stv[0]-1);
	for(int i=1;i<=stv[0]-1;++i)
	{
		printf("%.6lf %.6lf\n",a[stv[i]].first,a[stv[i]].second);
	}
}

int main()
{
	ifstream in("infasuratoare.in");
	freopen("infasuratoare.out","w",stdout);
	
	in>>n;
	for(int i=1;i<=n;++i)
	{
		in>>a[i].first>>a[i].second;
	}
	
	sort(a+1,a+n+1,cmp());
	
	make();
	
	return 0;
}