Cod sursa(job #788896)

Utilizator round2Test P round2 Data 16 septembrie 2012 01:11:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define Max 120001
#define Eps 1e-8
struct point{double x,y;}s[Max],s0[Max],s1[Max];
int n,n0,n1;
bool sort_type(point a,point b){return a.x<b.x;}

double delta(point a,point b,point c)
{return a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;}

void subsets()
{
    s0[0]=s1[0]=s[0];
    n0=n1=1;
    for(int i=1;i<n-1;i++)
    if(delta(s[0],s[n-1],s[i])>0)s0[n0++]=s[i]; else s1[n1++]=s[i];
    s0[n0++]=s1[n1++]=s[n-1];
}

void up_subset()
{
    n=2;
    for(int i=2;i<n0;i++)
    {
        while(n>=2 && delta(s0[n-2],s0[i],s0[n-1]) - Eps < 0)n--;
        s0[n++]=s0[i];
    }
    n0=n;
}

void down_subset()
{
    n=2;
    for(int i=2;i<n1;i++)
    {
        while(n>=2 && delta(s1[n-2],s1[i],s1[n-1]) + Eps > 0)n--;
        s1[n++]=s1[i];
    }
    n1=n;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%lf %lf",&s[i].x,&s[i].y);
    sort(s,s+n,sort_type);
    subsets();
    up_subset();
    down_subset();

    printf("%d\n",n0+n1-2);
    for(int i=n0-1;i>=0;i--)printf("%lf %lf\n",s0[i].x,s0[i].y);
    for(int i=1;i<n1-1;i++)printf("%lf %lf\n",s1[i].x,s1[i].y);

       // for(int i=0;i<n1;i++)printf("%lf %lf\n",s1[i].x,s1[i].y);

    return 0;
}