Cod sursa(job #739015)

Utilizator test0Victor test0 Data 21 aprilie 2012 22:11:17
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <algorithm>
#define MAX 120001
#define EPS 1e-12
using namespace std;

struct point{ long double x,y; }p[MAX],sus[MAX],jos[MAX],c[MAX];
int n,n1,n2,k;

long double det(point p1,point p2,point p3){
    return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y;
}

bool cmp(point p1,point p2){ return p2.x-p1.x>EPS; }

void desp(){
    point p1=p[1],p2=p[1];
    for(int i=1;i<=n;i++){
        if(p1.x-p[i].x>EPS)p1=p[i];
        if(p[i].x-p2.x>EPS)p2=p[i]; }
    sus[++n1]=p1;
    jos[++n2]=p1;
    for(int i=1;i<=n;i++)
    if(det(p1,p2,p[i])>0)sus[++n1]=p[i]; else
    if(det(p1,p2,p[i])<0)jos[++n2]=p[i];
    sus[++n1]=p2;
    jos[++n2]=p2;
}

void make_sus(){
    c[1]=sus[1]; c[2]=sus[2]; k=2;
    for(int i=3;i<=n1;i++){
        while(k>=2&&det(c[k-1],c[k],sus[i])+EPS>0)k--;
        c[++k]=sus[i];
    }
    for(int i=1;i<=k;i++)sus[i]=c[i];
    n1=k;
}

void make_jos(){
    c[1]=jos[1]; c[2]=jos[2]; k=2;
    for(int i=3;i<=n2;i++){
        while(k>=2&&det(c[k-1],c[k],jos[i])-EPS<0)k--;
        c[++k]=jos[i];
    }
    for(int i=1;i<=k;i++)jos[i]=c[i];
    n2=k;
}


int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%llf %llf",&p[i].x,&p[i].y);
    desp();
    sort(sus+1,sus+n1+1,cmp);
    sort(jos+1,jos+n2+1,cmp);
    make_sus();
    make_jos();

    printf("%d\n",n1+n2-2);
    for(int i=1;i<=n2;i++)printf("%llf %llf\n",jos[i].x,jos[i].y);
    for(int i=n1-1;i>1;i--)printf("%llf %llf\n",sus[i].x,sus[i].y);
}