Cod sursa(job #659511)

Utilizator lily3Moldovan Liliana lily3 Data 10 ianuarie 2012 18:20:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<algorithm>
using namespace std;

int i,j,n,m,s[120010],poz,k;
struct puncte
{
	double x,y,p;
};
puncte a[120010],b,aux;
int cmp(puncte a,puncte b)
{
	if(a.p==b.p)
		return a.x<b.x;
	return a.p<b.p;
}
int convex()
{
	puncte a1,a2,a3;
	double s1;
	a1=a[s[k-1]];
	a2=a[s[k]];
	a3=a[i];
	s1=(a1.x-a3.x)*(a2.y-a1.y)+(a1.x-a2.x)*(a1.y-a3.y);
	if(s1>0)
		return 1;
	return 0;
}
	
int main()
{
	FILE *f=fopen("infasuratoarea.in","r");
	FILE *g=fopen("infasuratoarea.out","w");
	fscanf(f,"%d",&n);
	b.x=b.y=1<<30;
	for(i=1;i<=n;++i)
	{
		fscanf(f,"%lf%lf",&a[i].x,&a[i].y);
		if(a[i].x<b.x||(a[i].x==b.x&&a[i].y<b.y))
			b=a[i],poz=i;
	}
	aux=a[poz],a[poz]=a[1],a[1]=aux;
    for(i=2;i<=n;++i)
		a[i].p=(a[i].y-b.y)/(a[i].x-b.x);
	sort(a+2,a+n+1,cmp);
	s[1]=1,s[2]=2,k=2;
	for(i=3;i<=n;++i)
	{
		while(!convex()&&k>2)
			k--;
		s[++k]=i;
	}
	fprintf(g,"%d\n",k);
	for(i=1;i<=k;++i)
		fprintf(g,"%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
	return 0;
}