Cod sursa(job #2284036)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 16 noiembrie 2018 17:34:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000006
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point{
                double x, y;
            }v[120005], a, s[120005];

int n, vf;

bool cmp(point b, point c)
{
    double x=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    if(x==0) return b.y<c.y||(b.y==c.y&&b.x<c.x);
    else return x<0;
}

int main()
{
    a.x=INF, a.y=INF;
    fin>>n;
    for(int i=1;i<=n;++i)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<a.y) a=v[i];
        else if(v[i].y==a.y&&v[i].x<a.x) a=v[i];
    }
    sort(v+1, v+n+1, cmp);
    v[n+1]=v[1], v[n+2]=v[2];
    a=v[1];
    point b=v[2], c=v[3];
    s[++vf]=v[1];
    s[++vf]=v[2];
    for(int i=3;i<=n+2;++i)
    {
        a=s[vf-1], b=s[vf], c=v[i];
        if(!cmp(b, c)) s[vf]=c;
        else s[++vf]=c;
    }
    fout<<vf-2<<"\n";
    fout<<fixed;
    for(int i=vf-1;i>=2;--i) fout<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<"\n";
    return 0;
}