Cod sursa(job #1606072)

Utilizator Darius15Darius Pop Darius15 Data 19 februarie 2016 20:05:56
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
long double x[120001],y[120001];
int p,n,i,ind[120001],j,var,st[120001];
bool semn(int i1,int i2,int i3)
{
    return (x[i2]-x[i1])*(y[i3]-y[i1])-(y[i2]-y[i1])*(x[i3]-x[i1])<0;
}
bool cmp(int a,int b)
{
    return (x[b]-x[p])*(y[a]-y[p])<(x[a]-x[p])*(y[b]-y[p]);
}
int main()
{
    f>>n;
    x[0]=1<<31-1,y[0]=1<<31-1;
    for (i=1;i<=n;i++){
        f>>x[i]>>y[i];
        if (x[p]>x[i] || (x[p]==x[i] && y[i]<y[p]))
            p=i;
    }
    for (i=1;i<=n;i++)
        if (i!=p)
        ind[++j]=i;
    sort(ind+1,ind+n,cmp);
    st[var=1]=p;
    for (i=1;i<=n-1;i++){
        while(var>=2 && semn(st[var-1],st[var],ind[i]))
        var--;
        st[++var]=ind[i];
    }
    g<<var<<'\n';
    g<<fixed<<setprecision(12);
    for (i=1;i<=var;i++)
        g<<x[st[i]]<<' '<<y[st[i]]<<'\n';
    return 0;
}