Cod sursa(job #1226597)

Utilizator YoChinezuWeng Mihai Alexandru YoChinezu Data 6 septembrie 2014 13:16:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const double eps=1.e-12;

class point{
    private: double x,y;
    public:
        point(){
            x=0;
            y=0;
        }
        point(double xx,double yy){
            x=xx;
            y=yy;
        }
        double getx(){
            return x;
        }
        double gety(){
            return y;
        }
        bool ccw(const point &p2,const point &p3){
            return (p2.x-x)*(p3.y-p2.y)-(p2.y-y)*(p3.x-p2.x)>=eps;
        }
};

point v[120001];
int sol[120001];

bool cmp(point a,point b){
    if(v[0].ccw(a,b)){
        return 1;
    }
    return 0;
}

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

    int n,top;
    double x,y;
    scanf("%d%lf%lf",&n,&x,&y);
    point ll(x,y);
    v[0]=ll;
    for(int i=1;i<n;++i){
        scanf("%lf%lf",&x,&y);
        point aux(x,y);
        v[i]=aux;
        if(((fabs(y-v[0].gety())<eps)&&(x-v[0].gety()<=-eps))||(y-v[0].gety()<=-eps)){
            swap(v[0],v[i]);
        }
    }

    sort(v+1,v+n,cmp);
    v[n]=v[0];

    sol[0]=0;
    sol[1]=1;
    top=1;
    int i=2;

    while(i<=n){
        if(v[sol[top-1]].ccw(v[sol[top]],v[i])){
            sol[++top]=i;
            ++i;
        }
        else
            --top;
    }

    printf("%d\n",top);
    for(int i=0;i<top;++i){
        printf("%lf %lf\n",v[sol[i]].getx(),v[sol[i]].gety());
    }

    return 0;
}