Cod sursa(job #379872)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 4 ianuarie 2010 12:22:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<stdio.h>
#include<algorithm>
int mini;
using namespace std;
#define nmax 120002
struct point
{double x,y;};
int n,st[nmax],o[nmax];
point v[nmax];

bool cmp(int i, int j)
{
	return ((v[i].y-v[mini].y)*(v[j].x-v[mini].x))<((v[j].y-v[mini].y)*(v[i].x-v[mini].x));
}

int semn(point p1, point p2, point p3)
{
	double s;
	s=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
	if(s<0)
		return -1;
	if(s>0)
		return 1;
	return 0;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	int i;
	v[mini].x=v[mini].y=1000000000;
	for(i=1;i<=n;i++)
	{
		scanf("%lf%lf",&v[i].x,&v[i].y);
		if(v[i].x<v[mini].x || (v[i].x==v[mini].x && v[i].y<v[mini].y))
			mini=i;
	}
	for(i=1;i<mini;i++)
		o[i]=i;
	for(i=mini+1;i<=n;i++)
		o[i-1]=i;
	sort(o+1,o+n,cmp);
	st[++st[0]]=mini;
	for(i=1;i<n;i++)
	{
		while(st[0]>=3 && semn(v[st[st[0]-1]],v[st[st[0]]],v[o[i]])==-1)
			st[0]--;
		st[++st[0]]=o[i];
	}
	printf("%d\n",st[0]);
	for(i=1;i<=st[0];i++)
		printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
	return 0;
}