Cod sursa(job #767514)

Utilizator test_666013Testez test_666013 Data 13 iulie 2012 18:24:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 120002
#define EPS 1e-12

struct punct{ long double x,y; }s[MAX],st[MAX],dr[MAX];

int n,n_st,n_dr;

bool sort_mode(punct a,punct b){ return a.x < b.x; }

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

void subsets(){
    st[0] = dr[0] = s[0];

    for(int i=1;i<n-1;i++)
    if( delta( s[0], s[n-1], s[i] ) > 0 ) st[++n_st] = s[i]; else dr[++n_dr] = s[i];

    st[++n_st] = dr[++n_dr] = s[n-1];
    n_st ++;
    n_dr ++;
}

void up_subset(){
    int n = 2;

    for(int i=2;i<n_st;i++)
    {
        while( n >= 2 && delta( st[n-2], st[i], st[n-1] ) - EPS < 0 )n--;
        st[n++] = st[i];
    }
    n_st = n;
}

void down_subset(){
    int n = 2;

    for(int i=2;i<n_dr;i++)
    {
        while( n >= 2 && delta( dr[n-2], dr[i], dr[n-1] ) + EPS > 0 )n--;
        dr[n++] = dr[i];
    }
    n_dr = n;
}

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

    sort(s,s+n,sort_mode);
    subsets();
    up_subset();
    down_subset();

    printf("%d\n",n_st+n_dr-2);

    for(int i=n_st-1;i>=0;i--)printf("%llf %llf\n",st[i].x,st[i].y);
    for(int i=1;i<n_dr-1;i++)printf("%llf %llf\n",dr[i].x,dr[i].y);

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


    return 0;
}