Cod sursa(job #2778171)

Utilizator DVDPRODavid D DVDPRO Data 29 septembrie 2021 19:01:47
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct punct{
    long double x, y;
}p[120000], stiva[120000];

int TheChosenOne, n, ns;

long double determinant(punct a, punct b, punct c) {
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void read()
{
    fin>>n;
    for(int i=0; i<n; i++)
        {
            fin>>p[i].x>>p[i].y;
            if(p[i].x<p[TheChosenOne].x)
                TheChosenOne=i;
            if(p[i].x==p[TheChosenOne].x)
                if(p[i].y<p[TheChosenOne].y)
                    TheChosenOne=i;
        }
        swap(p[0], p[TheChosenOne]);
}

bool custom(punct a, punct b)
{
    return determinant(p[0], a, b)>0;
}

void LeSorteAuChocolat()
{
    sort(p, p+n, custom);
   // for(int i=0; i<n; i++)
     //   cout<<p[i].x<<" "<<p[i].y<<'\n';
}

void ActualWork()
{
    stiva[0]=p[0];
    stiva[1]=p[1];
    ns=2;
    for (int i=2; i<n; i++) {
        while (determinant(stiva[ns-2], stiva[ns-1], p[i])<=0)
            ns--;
        stiva[ns++]=p[i];
    }
}
void afisare()
{
    fout<<ns<<'\n';
    for(int i=1; i<ns; i++)
        fout<<fixed<<setprecision(6)<<stiva[i].x <<" "<<stiva[i].y<<'\n';

     fout<<fixed<<setprecision(6)<<stiva[0].x <<" "<<stiva[0].y<<'\n';
}
int main()
{
    read();
    LeSorteAuChocolat();
    ActualWork();
    afisare();
    return 0;
}