Cod sursa(job #1830960)

Utilizator vancea.catalincatalin vancea.catalin Data 17 decembrie 2016 11:48:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
#define DX 120050
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
int n;
struct str
{
    double x,y;
};
str p[DX],r[DX];
double det(str p,str a,str b)
{
    return p.x*a.y+b.x*p.y+a.x*b.y-b.x*a.y-p.x*b.y-a.x*p.y;
}
bool cmp(str a,str b)
{
    return (det(p[0],a,b)>=0);
}
int main()
{
    double x,y,mx=9999999,my=9999999;
    int ind,i,n,lr;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        p[i]={x,y};
        if(mx>x || (mx==x && my>y))
        {
            mx=x;my=y;ind=i;
        }
    }
    p[0]=p[ind]; p[ind]=p[n];
    sort(p+1,p+n,cmp);
    r[0]=p[0]; r[lr=1]=p[1];
    for(i=2;i<n;i++)
    {

        while(lr>1 && det(r[lr-1],r[lr],p[i])<0)
        {
            lr--;
        }
        lr++;
        r[lr]=p[i];
    }
    fout<<lr+1<<"\n"<<fixed;
    for(i=0;i<=lr;i++)
    {
        fout<<setprecision(12)<<r[i].x<<" "<<setprecision(12)<<r[i].y<<"\n";
    }
}