Cod sursa(job #2063374)

Utilizator sebi110Ciobanu Sebastian sebi110 Data 11 noiembrie 2017 11:09:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct{
    long double x,y;
    };
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
punct stiva[120000];
int n,vf=1;
punct a[120000];
int compara2(punct a,punct b)
{
    return (a.x<b.x) || (a.x==b.x && a.y<b.y);
}
int compara(punct a,punct b)
{
    long double m1=a.y;
    long double m2=b.y;
    m1=m1/(a.x);
    if(a.x==0)
        m1=3;
    m2=m2/(b.x);
    if(b.x==0)
        m2=3;
    return m1<=m2;
}
char sarie(punct a,punct b,punct c)
{
    long double z;
    z=a.x*b.y+b.x*c.y+a.y*c.x;
    z=z-b.y*c.x-a.y*b.x-c.y*a.x;
    if(z<-0.00000001)
        return 1;
    return 0;
}
void solution()
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        while(vf>=2 &&sarie(stiva[vf-1],stiva[vf],a[i])==1)
            vf--;
        stiva[++vf]=a[i];
    }
}
int main()
{
    int i,indmin=1;
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>a[i].x>>a[i].y;
        if(a[indmin].x>a[i].x)
            indmin=i;
        else
            if(a[indmin].x==a[i].x && a[indmin].y>a[i].y)
                indmin=i;
    }
    swap(a[1],a[indmin]);
    stiva[1].x=a[1].x;
    stiva[1].y=a[1].y;
    for(i=2;i<=n;i++)
    {
        a[i].x-=a[1].x;
        a[i].y-=a[1].y;
    }
    sort(a+2,a+1+n,compara);
    for(i=2;i<=n;i++)
    {
        a[i].x+=a[1].x;
        a[i].y+=a[1].y;
    }
    solution();
    fout<<vf<<'\n';
    for(i=1;i<=vf;i++)
        fout<<setprecision(15)<<stiva[i].x<<' '<<setprecision(15)<<stiva[i].y<<'\n';
    return 0;
}