Cod sursa(job #932497)

Utilizator dariusgDarius Galis dariusg Data 28 martie 2013 23:09:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <algorithm>
using namespace std;

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

#define eps 1e-12
#define Nmax 120001

int n,i,h,k;

struct punct {
	double x,y;
}p[Nmax],v[Nmax],minx;

int s[Nmax],ok[Nmax];


inline int cmp1(double a,double b) {
	if (a+eps<b) return 1;
	if (b+eps<a) return -1;
	return 0;
}


bool cmp(const punct &a,const punct &b) 
{
	int t;
	t=cmp1(a.x,b.x);
	if (t!=0) return t==1;
	return (cmp1(a.y,b.y)==1);
}


int semn(punct a,punct b,punct c) 
{
	return cmp1((a.y-b.y)*c.x+(b.x-a.x)*c.y+a.x*b.y - b.x*a.y,0);
}

void rezolva()
{
	int k,q;
	sort(v+1,v+n+1,cmp);
	
	s[1]=1; s[2]=2; 
	ok[2]=1;
	
	k=2; 
	i=3; 
	q=1;
	
	while (!ok[1])
	{
		while (ok[i])
		{
			if (i==n) q=-1;
			i+=q;
		}
		while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
		{
			ok[s[k--]]=0;
		}
		s[++k]=i;
		ok[i]=1;
	}
	h=k-1;
}

int main ()
 {
	fscanf(f,"%d",&n);
	
	for (i=1; i<=n; i++)
		fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
		
	rezolva();
	
	fprintf(g,"%d\n",h);

	
	for(i=h+1;i>=2;i--)
        fprintf(g,"%lf %lf\n",v[s[i]].x,v[s[i]].y);
    fclose(f);
    fclose(g);
	return 0;
}