Cod sursa(job #2286748)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 20 noiembrie 2018 17:53:55
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 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;
}

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)
        {
            lolo=v[i];
        }
        if(v[i].y==lolo.y && lolo.x<v[i].x)
        {
            lolo=v[i];
        }
    }
    sort(v.begin(),v.end(),cmp_trigo);
    for(int i=0;i<n;i++)
    {
        if(v[i].x==lolo.x && v[i].y==lolo.y)
        {
            swap(v[i],v[0]);
            break;
        }
    }
    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;
}
/**

**/