Cod sursa(job #407605)

Utilizator hadesgamesTache Alexandru hadesgames Data 2 martie 2010 14:46:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include<algorithm>
using namespace std;
#define fi first
#define se second
pair<double,double > a[120050];
int q[120050],v[120050];
const double eps=0.000000000001;
FILE *in,*out;
int parte(int i,int j,int k)
{
	double A=a[i].se-a[j].se;
	double B=a[j].fi-a[i].fi;
	double C=a[i].fi*a[j].se-a[i].se*a[j].fi;
	double rez=A*a[k].fi+B*a[k].se+C;
	if (-eps<=rez&&rez<=eps)
		return 0;
	if (rez<0)
		return -1;
	return 1;
}
int main()
{
	int i,n,pas,u;
	in=fopen("infasuratoare.in","r");
	out=fopen("infasuratoare.out","w");
	fscanf(in,"%d",&n);
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%lf %lf",&a[i].fi,&a[i].se);
	}
	sort(a+1,a+n+1);
	pas=1;
	q[u=1]=1;
	v[1]=1;
	for (i=1;i>=1;i+=pas)
	{
		if (i==n)
		{
			pas=-1;
			v[1]=0;
		}
		if (v[i])
			continue;
		while (u>1&&parte(q[u-1],i,q[u])==1)
		{
			v[q[u]]=0;
			u--;
		}
		u++;
		q[u]=i;
		v[i]=1;
	}
	fprintf(out,"%d\n",u-1);
	for(i=1;i<u;i++)
		fprintf(out,"%lf %lf\n",a[q[i]].fi,a[q[i]].se);
	fclose(in);
	fclose(out);
	return 0;
}