Cod sursa(job #536430)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 18 februarie 2011 17:26:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define max 1000000001
#define Nmax 120005 
#define er 1e-12
#define f first
#define s second
#define pr pair<double,double>

using namespace std;

int q,k,nr,i,j,m,n;
pr a[Nmax],W[Nmax];
int b[Nmax],ok[Nmax];

int cmp2(double a,double b)
{
	if (fabsf(a-b)<er) return 0;
	if (a>b) return 1;
	return -1;
}

int cmp(const pr a,const pr b)
{
    int q=cmp2(a.f,b.f);
    if (q!=0) return q==-1; 
    return cmp2(a.s, b.s)==-1;
}

int semn(pr a,pr b,pr c)
{ 
    return cmp2((a.s-b.s)*c.f+(b.f-a.f)*c.s+(a.f*b.s-b.f*a.s),0);
}

void rezolva()
{
	int q=1;
    sort(a+1,a+n+1,cmp);
    ok[2]=1; 
	b[1]=1; 
	b[2]=2; 
	k = 2; 
	i = 3;
    while (!ok[1])
    {
        while (ok[i])
        {
            if (i==n) q=-1;
            i+=q;
        }
        while (k>=2&&semn(a[b[k-1]],a[b[k]],a[i])==-1)
            ok[b[k--]]=0;
        b[++k]=i;
		ok[i]=1;
    }
	nr=k-1;
	for (i=1;i <= nr;++i)
        W[i] = a[b[i]];
    W[nr+1] = W[1];

}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%lf %lf",&a[i].f,&a[i].s);
	    
	rezolva();  
	
	printf("%d\n",nr); 
	for (i=1;i<=nr;i++)
		printf("%.6lf %.6lf\n",W[i].f,W[i].s);
	printf("\n");
	return 0; 
}