Cod sursa(job #927345)

Utilizator taigi100Cazacu Robert taigi100 Data 25 martie 2013 19:03:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define max 120005
typedef pair<double,double> point;
int n,head;
point v[max],stack[max];

double cross_product(const point &a,const point &b,const point &c)
{
	return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}

int comp(const point &a,const point &b)
{
	return cross_product(v[1],a,b)<0;
}

void Read()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf %lf",&v[i].first,&v[i].second);
}

void Sort_Points()
{
	int pos=1;
	for(int i=2;i<=n;i++) if(v[i]<v[pos]) pos=i;
	swap(v[1],v[pos]);
	sort(v+2,v+n+1,comp);
}
void Solve()
{
	Sort_Points();
	stack[1]=v[1];
	stack[2]=v[2];
	head=2;
	for(int i=3;i<=n;++i)
	{
		while( head>=2 && ( cross_product(stack[head-1],stack[head],v[i]) > 0 ) )
			--head;
		stack[++head]=v[i];
	}
}

void Print()
{
	printf("%d\n",head);
	for(int i=head;i>=1;i--)
		printf("%.9lf %.9lf\n",stack[i].first,stack[i].second);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);

	Read();
	Solve();
	Print();

	return 0;
}