Cod sursa(job #2173144)

Utilizator novistaAlex Staicu novista Data 15 martie 2018 20:53:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define Lmax 120003
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
    double x,y;
}a[Lmax],s[Lmax];
int n,i,k;
bool cmp(punct a, punct b)
{
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    return false;
}
int det(punct a,punct b, punct c)
{
    if((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y)>=0)
        return 1;
    return 0;
}
int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    s[1]=a[1];
    k=1;
    for (i=2;i<=n;i++)
    {
        while (k>1&&!det(s[k-1],s[k],a[i]))
            k--;
        k++;
        s[k]=a[i];
    }
    for (i=n-1;i>=1;i--)
    {
        while (!det(s[k-1],s[k],a[i]))
            k--;
        k++;
        s[k]=a[i];
    }
    fout<<fixed<<setprecision(6);
    fout<<k-1<<"\n";
    for(i=1;i<=k-1;i++) fout<<s[i].x<<" "<<s[i].y<<"\n";
    fin.close();
    fout.close();
    return 0;
}