Cod sursa(job #2231289)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 13 august 2018 17:58:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,solve[150000];
struct poz{
    double x;
    double y;
};
poz v[150000];
bool comp(poz a, poz b)
{
    if(a.x<b.x)
        return true;
    else if(a.x==b.x && a.y<b.y)
        return true;
    return false;
}
bool ok(int a, int b, int c)
{
    double delta,a1=v[a].x,a2=v[b].x,a3=v[c].x,b1=v[a].y,b2=v[b].y,b3=v[c].y;
    delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
    if(delta<0)
        return false;
    else
        return true;
}
int main()
{
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v+1,v+1+n,comp);
    solve[1]=1;
    solve[2]=2;
    int k=2;
    for(int i=3; i<=n; i++)
    {
        if(ok(solve[k],solve[k-1],i))
        {
            solve[++k]=i;
        }
        else
        {
            while(!ok(solve[k],solve[k-1],i) && k>=2)
            {
                k--;
            }
            solve[++k]=i;
        }
    }
    solve[++k]=n-1;
    for(int i=n-2; i>=1; i--)
    {
        if(ok(solve[k],solve[k-1],i))
        {
            solve[++k]=i;
        }
        else
        {
            while(!ok(solve[k],solve[k-1],i) && k>=2)
            {
                k--;
            }
            solve[++k]=i;
        }
    }
    out << k-1 << '\n';
    for(int i=k-1; i>=1; i--)
    {
        out << fixed << setprecision(6) << v[solve[i]].x << ' ' << fixed << setprecision(6) << v[solve[i]].y << '\n';
    }
    return 0;
}