Cod sursa(job #2128978)

Utilizator natrovanCeval Marius natrovan Data 12 februarie 2018 12:59:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include<iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n,i,j,k;

struct punct
{
    double x;
    double y;
};

double determinant(punct a, punct b, punct c)
{
   return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(b.y*c.x)-(a.x*c.y)-(b.x*a.y));
}
punct P[120003],S[120003];

bool comp(punct i, punct j)
{
    if (determinant(P[1],i,j)>0) return true;
    return false;
}


int main()
{
    fin>>n;
    fin>>P[1].x>>P[1].y;
    j=1;
    for(i=2;i<=n;++i)
    {
        fin>>P[i].x>>P[i].y;
        if(P[i].x<P[j].x||(P[i].x==P[j].x&&P[i].y<P[j].y))j=i;
    }
    swap(P[1],P[j]);
    sort(P+2,P+1+n,comp);

    S[1]=P[1];
    S[2]=P[2];
    k=2;

    for(i=3;i<=n;++i)
    {
        while(determinant(S[k-1],S[k],P[i])<0)k--;

        ++k;
        S[k]=P[i];
    }

    fout<<k<<'\n';
fout<<fixed;
    for(i=1;i<=k;++i)
    {
        fout<<setprecision(6)<<S[i].x<<' '<<setprecision(6)<<S[i].y;
        fout<<'\n';
    }

    return 0;
}