Cod sursa(job #752516)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 28 mai 2012 19:46:58
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,l1,l2;
typedef pair<double,double> pdd;
pdd v1[100100],v2[100100],a[100100],a1[100100],a2[100100];

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)
{
	//cout<<a.first<<' '<<a.second<<"   "<<b.first<<' '<<b.second<<"   "<<c.first<<' '<<c.second<<": ";
	//cout<<"    "<<(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)<<"   ";
	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 0;
	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;//{cout<<" 1\n";return 1;}
	return -1;
	//cout<<"-1\n";return -1;
}

inline int make(int semn,pdd v[],int unu,int doi,pdd a[])
{
	int lf=0;
	
	pdd p1,p2,p3;
	p1=a[1];
	p2=a[2];
	p3=a[3];
	
	//cout<<semn<<'\n';
	
	v[++lf]=a[1];
	for(int i=2,j=unu;j<doi;++j,++i)
	{
		if(semiplan(p1,p3,p2)==semn)
		{
			v[++lf]=a[i];
			p1=p2;
			p2=p3;
			p3=a[i+2];
			//cout<<i<<'\n';
		}
		else
		{
			p2=p3;
			p3=a[i+2];
		}
	}
	
	//cout<<'\n';
	return lf;
}

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());
	
	a1[++l1]=a2[++l2]=a[1];
	for(int i=2;i<n;++i)
	{
		if(semiplan(a[1],a[n],a[i])<0)
		{
			a1[++l1]=a[i];
		}
		else
		{
			a2[++l2]=a[i];
		}
	}
	
	
	a1[++l1]=a2[++l2]=a[n];
	int lt1,lt2;
	lt1=lt2=0;
	
	//cout<<"\n\n\n";
	lt1=make(-1,v1,1,l1,a1);
	lt2=make(1,v2,1,l2,a2);
	
	printf("%d\n",lt1+lt2-2);
	
	for(int i=1;i<=lt1;++i)
	{
		printf("%.6lf %.6lf\n",v1[i].first,v1[i].second);
	}
	for(int i=2;i<lt2;++i)
	{
		printf("%.6lf %.6lf\n",v2[i].first,v2[i].second);
	}
	
	return 0;
}