Cod sursa(job #729873)

Utilizator ILDottoreBogdan Stoian ILDottore Data 30 martie 2012 16:22:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<algorithm>
using namespace std;

#define NMAX 120005
#define INF 2000000000

FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");

long N, PCT[NMAX],S[NMAX],init,vf;
double X[NMAX],Y[NMAX],st=INF,jos=INF;


struct cmp {
	bool operator() (long i,long j)
	{ return ( X[i]-X[init]) * (Y[j]-Y[init]) < (X[j]-X[init]) *(Y[i]-Y[init]) ;}
			};	

double unghi_stanga( long i1, long i2,long i3)
{
	return (double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}

int main()
{
	fscanf(f,"%ld",&N);
	for (long i=1;i<=N;i++)
	{  fscanf(f,"%lf%lf", &X[i], &Y[i]);
		if (X[i]<st || ( X[i]==st && Y[i] < jos ) )
			{ init=i;
		      st=X[i]; jos=Y[i];
			}
	}
	
	for (long i=1;i<=N;i++)
	{ if (i==init) continue;
	  PCT[ ++PCT[0] ] = i;
	}
	
	sort ( PCT+1, PCT+PCT[0]+1 , cmp() );
	
	vf=3;
	S[1]=init;
	S[2]= PCT[1];
	S[3]= PCT[2];
	   
	for (long i=3;i<=PCT[0];i++)
	{  long p = PCT[i];
	   
	while( vf>=2 && unghi_stanga ( S[vf],S[vf-1],p) <0 ) vf--;

	S[++vf]=p;
	}
	   
	
	fprintf(g,"%ld\n",vf);
	for (long i=vf;i>=1;i--)
	fprintf(g,"%lf %lf\n",X[S[i]],Y[S[i]]);
return 0;}