Cod sursa(job #753665)

Utilizator SmarandaMaria Pandele Smaranda Data 30 mai 2012 11:31:47
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <cstdio>
#include <math.h>
#define eps 1.e-12
using namespace std;

struct Point {
    double x,y;
    void operator = (const Point & other) {
        x=other.x;
        y=other.y;
    }
};
Point P[120008];
Point ll;
Point h[120008];

double dist (Point A , Point B) {
    return sqrt(((double)A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

long ccw (Point A , Point B , Point C) {
    double cp;
    cp=(B.x-A.x)*(C.y-B.y)-(B.y-A.y)*(C.x-B.x);
    if (fabs(cp)<eps)
        return 0;
    else
        if (cp<=-eps)
            return -1;
        else return 1;
}


bool comp (Point A , Point B  , Point C) {
    long cp;
    double d1,d2;
    cp=ccw(A,B,C);
    if (cp==0) {
        d1=dist(A,C);
        d2=dist(A,B);
        if (d1-d2>eps)
            return 1;
        else return 0;
    }
    else
        if (cp==1)
            return 1;
        else return 0;
}

bool samepoint (Point A  , Point B) {
    return (fabs(A.x-B.x)<eps && fabs(B.y-A.y)<eps);
}

long part (long st , long dr) {
    long i,j,m;
    Point aux,piv;
    m=(st+dr)/2;
    piv=P[m];
    i=st-1;
    j=dr+1;
    while (1) {
        do {++i;}while (!samepoint(piv,P[i]) && comp(ll,P[i],piv));
        do {--j;}while (!samepoint(piv,P[j]) && comp(ll,piv,P[j]));
        if (i<j) {
            aux=P[i];
            P[i]=P[j];
            P[j]=aux;
        }
        else return j;
    }
}

void quick (long st  , long dr) {
    long sp;
    if (st<dr) {
        sp=part(st,dr);
        quick(st,sp);
        quick(sp+1,dr);
    }
}

int main () {
    long n,poz,i,cp,u,st,dr;
    Point aux;

    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);

    scanf("%ld",&n);
    scanf("%lf%lf",&P[1].x,&P[1].y);
    ll=P[1];
    poz=1;
    for (i=2;i<=n;i++) {
        scanf("%lf%lf",&P[i].x,&P[i].y);
        if (P[i].y-ll.y<=-eps || (fabs(P[i].y-ll.y)<eps && P[i].x-ll.x<=-eps)) {
            ll=P[i];
            poz=i;
        }
    }
    aux=P[poz];
    P[poz]=P[1];
    P[1]=aux;
    quick(1,n);
    P[n+1]=P[1];
    h[1]=P[1];
    h[2]=P[2];
    u=2;
    i=3;
    while (i<=n+1) {
        cp=ccw(h[u-1],h[u],P[i]);
        if (cp>0)  {
            h[++u]=P[i];
            i++;
        }
        else u--;
    }
    u--;
    printf("%ld\n",u);
    for (i=1;i<=u;i++)
        printf("%lf %lf\n",h[i].x,h[i].y);
    return 0;
}