Cod sursa(job #1632316)

Utilizator TrascaAndreiTrasca Andrei TrascaAndrei Data 6 martie 2016 00:25:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct
{
    double x,y;
}p[120005];

int n,vf,s[120005];

inline double det(punct a,punct b,punct c)
{
    return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}

inline bool cmp(punct a,punct b)
{
    return det(a,b,p[1])>0;
}

int main()
{
    fin>>n;
    int i,poz=1;
    for(i=1;i<=n;i++)
    {
        fin>>p[i].x>>p[i].y;
        if(p[poz].x>p[i].x || (p[poz].x==p[i].x && p[poz].y>p[i].y))
            poz=i;
    }
    swap(p[1],p[poz]);
    sort(p+2,p+n+2,cmp);
    s[++vf]=1;s[++vf]=2;
    for(i=3;i<=n;i++)
    {
        while(vf>=2 && det(p[s[vf-1]],p[s[vf]],p[i])<0)
            vf--;
        s[++vf]=i;
    }
    fout<<vf<<'\n';
    for(i=vf;i>=1;i--)
        fout<<setprecision(6)<<fixed<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
    return 0;
}