Cod sursa(job #1879718)

Utilizator danysilas23Silas Daniel danysilas23 Data 15 februarie 2017 09:37:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda becreative16 Marime 0.81 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define P pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
P v[1<<17],s[1<<17];
int n,k,i,j;
inline bool ok(P a,P b,P c)
{
    return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))<0;
}
bool cmp(P a,P b)
{
    return (!ok(v[1],a,b));
}
int main()
{
    f>>n;
    for(i=j=1;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].y<v[j].y||(v[i].y==v[j].y&&v[i].x<v[j].x)) j=i;
    }
    swap(v[1],v[j]);
    sort(v+2,v+n+1,cmp);
    s[++k]=v[1];
    s[++k]=v[2];
    for(i=3;i<=n;++i)
    {
        while(k>=2&&ok(s[k-1],s[k],v[i])) k--;
        s[++k]=v[i];
    }
    g<<k<<'\n';
    for(i=1;i<=k;++i)
        g<<fixed<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
    return 0;
}