Cod sursa(job #2286758)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 20 noiembrie 2018 18:05:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

#include <algorithm>

#include <iomanip>



using namespace std;



typedef long double ld;



struct point

{

    ld x;

    ld y;

};



ld cp(point p1,point p2,point p3)

{

    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);

}



ld area(point p1,point p2,point p3)

{

    return fabs(0.5*cp(p1,p2,p3));

}



point lolo;



ld dpp(point p1,point p2)

{

    ld dx=p1.x-p2.x;

    ld dy=p2.y-p2.y;

    return dx*dx+dy*dy;

}



bool cmp_trigo(point p1,point p2)

{

    if(cp(lolo,p1,p2)==0)

    {

        return dpp(lolo,p1)<dpp(lolo,p2);

    }

    else

    {

        return cp(lolo,p1,p2)>0;

    }

}



int n;



const int N=120000+5;



point st[N];

int vf;



inline void add(point a)

{

    while(vf>=2 && cp(st[vf-1],st[vf],a)<=0)

    {

        vf--;

    }

    st[++vf]=a;

}


const ld EPS=1e-14;


int main()

{

    freopen("infasuratoare.in","r",stdin);

    freopen("infasuratoare.out","w",stdout);

    lolo={1000000000,1000000000};

    cin>>n;

    vector<point>v(n);

    for(int i=0;i<n;i++)

    {

        cin>>v[i].x>>v[i].y;

        if(v[i].y-lolo.y<=-EPS)

        {

            lolo=v[i];
            swap(v[i],v[0]);

        }
        else
        if(fabs(v[i].y-lolo.y)<EPS && lolo.x-v[i].x<=-EPS)

        {

            lolo=v[i];
            swap(v[i],v[0]);
        }

    }

    sort(v.begin()+1,v.end(),cmp_trigo);



    for(int i=0;i<=n;i++)

    {

        add(v[i%n]);

    }

    cout<<vf-1<<"\n";

    for(int i=1;i<vf;i++)

    {

        cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";

    }

    return 0;

}

/**

{1}

**/