Cod sursa(job #2284269)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 17 noiembrie 2018 09:36:42
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,k;
struct ceva
{
    double x,y;
}v[120002],s[120002];
int det(double xa,double ya,double xb,double yb,double xc,double yc)
{
    if((xb-xa)*(yc-ya)-(xc-xa)*(yb-ya)>=0)return 1;
    else return 0;
}
int cmp(ceva a,ceva b)
{
    if(a.x<b.x || (a.x==b.x && a.y<b.y))return true;
    return false;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    s[1]=v[1];
    k=1;
    for(i=2;i<=n;i++)
    {
        while(k>1 && det(s[k-1].x,s[k-1].y,s[k].x,s[k].y,v[i].x,v[i].y))
        {
            k--;
        }
        k++;
        s[k]=v[i];
    }
    for(i=n-1;i>=1;i--)
    {
        while(!det(s[k-1].x,s[k-1].y,s[k].x,s[k].y,v[i].x,v[i].y))
        {
            k--;
        }
        k++;
        s[k]=v[i];
    }
    g<<setprecision(6)<<fixed;
    g<<k-1<<'\n';
    for(i=1;i<=k-1;i++)
    {
        g<<s[i].x<<" "<<s[i].y<<'\n';
    }
    return 0;
}