Cod sursa(job #2128971)

Utilizator Cristian.BBurghelea Cristian Cristian.B Data 12 februarie 2018 12:55:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct{double x;double y;}p[120005];
punct S[120005];

double determinant(punct a,punct b,punct c)
{
    return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x;
}

bool verifica(punct i,punct j)
{
    double d;
    d=determinant(p[1],i,j);
    if(d>0)return true;
    else return false;
}

int i,j,n,k;
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+n+1,verifica);
    S[1]=p[1]; S[2]=p[2]; k=2;
    for(i=3;i<=n;++i)
    {
        while(k>1 && determinant(S[k-1],S[k],p[i])<0)--k;
        S[++k]=p[i];
    }
    fout<<k<<'\n';
    fout<<fixed;
    for(i=2;i<=k;++i)
        fout<<setprecision(6)<<S[i].x<<' '<<setprecision(6)<<S[i].y<<'\n';
    fout<<setprecision(6)<<S[1].x<<' '<<setprecision(6)<<S[1].y<<'\n';


    fin.close(); fout.close();
    return 0;
}