Cod sursa(job #2285283)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 18 noiembrie 2018 13:35:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 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)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)<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];
    int nr=0;
    for(int i=3;i<=n+2;++i)
    {
        a=s[vf-1], b=s[vf], c=v[i];
        while(!cmp(b, c)&&vf>1)
        {
            vf--;
            nr--;
            a=s[vf-1];
            b=s[vf];
        }
        s[++vf]=c;
        nr++;
    }
    fout<<nr<<"\n";
    fout<<fixed;
    fout<<setprecision(12)<<s[1].x<<" "<<setprecision(12)<<s[1].y<<"\n";
    for(int i=nr;i>=2;--i) fout<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<"\n";
    return 0;
}