Cod sursa(job #2360289)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 1 martie 2019 17:34:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define Nmax 120005
#define ld long double
#define _point pair <ld,ld>
#define x first
#define y second

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

_point P[Nmax];
_point st[Nmax];
int N,k;

inline bool det(const _point &p1, const _point &p2, const _point &p3){

    return p1.x*p2.y-p1.y*p2.x+p2.x*p3.y-p2.y*p3.x+p3.x*p1.y-p3.y*p1.x<=0;
}

inline bool comp(const _point &lsh, const _point &rsh){

    return (lsh.y-P[1].y)*(rsh.x-P[1].x)<(lsh.x-P[1].x)*(rsh.y-P[1].y);
}

void read_data(){

    f>>N;
    int pos=1;
    for(int i=1;i<=N;i++){

        f>>P[i].x>>P[i].y;
        if(P[i]<P[pos])
            pos=i;
    }

    swap(P[1],P[pos]);
}

void solve(){

    sort(P+2,P+N+1,comp);

    st[++k]=P[1];
    st[++k]=P[2];
    for(int i=3;i<=N;i++){

        while(k>1 and det(st[k-1],st[k],P[i]))
            --k;
        st[++k]=P[i];
    }
}

void print_ans(){

    g<<k<<fixed<<setprecision(6)<<'\n';
    for(int i=1;i<=k;i++)
        g<<st[i].x<<' '<<st[i].y<<'\n';
}

int main(){

    read_data();
    solve();
    print_ans();

    return 0;
}