Cod sursa(job #764338)

Utilizator test666013Testez test666013 Data 4 iulie 2012 19:30:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 120001
#define EPS 1e-6

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

int n,n1,n2;

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.y * c.x - c.y * a.x - a.y * b.x; }

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

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

    st[n1++] = dr[n2++] = s[n-1];
}

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

void down_envelope(){
    int n = 2;
    for(int i=2;i<n2;i++)
    {
        while(n >= 2 && delta(dr[n-2],dr[i],dr[n-1]) > 0)n--;
        dr[n++] = dr[i];
    }
    n2 = 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_envelope();
    down_envelope();

    printf("%d\n",n1+n2-2);
    for(int i=0;i<n1;i++)printf("%lf %lf\n",st[i].x,st[i].y);
    for(int i=n2-2;i>0;i--)printf("%lf %lf\n",dr[i].x,dr[i].y);

    // for(int i=0;i<n;i++)printf("%lf %lf\n",s[i].x,s[i].y);
   /*  for(int i=0;i<n1;i++)printf("%lf %lf\n",st[i].x,st[i].y);
    printf("-----------------------------------------------\n");
     for(int i=0;i<n2;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);*/
    return 0;
}