Cod sursa(job #2718037)

Utilizator HannaLieb Hanna Hanna Data 8 martie 2021 13:18:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
/**
Konvex burkolo

Kivalasztom a legalso elemet, azok kozul is a legbaloldalibbat. Utana a tobbi elemet rendezem a szog szerint, amit
a legalso elem egyenesevel zar be. Ezt ugy csinalom, hogy a legalso elemet kitcserelem az elsovel, mert ugyis az kell
legyen az elso, es a tobbit sortolom. A sort-hoz hasznalom a fgv1-et, ami megmondja, hogy az elso elem, es az akt1 elem
altal letrehozott egyenestol az akt2 az jobbra vagy balra van.
Ezutan csinalom meg a konvex burkolot, hasonlo rendszer szerint haladva> ha az elozo ket pont altal alkotott egyeneshez kepest
az aktualis pont balra van, akkor beteszem a vegere, ha nem, akkor addig veszem az eloso ket part a burkolobol, amig rendben nem lesz.
**/

#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

using namespace std;

#define NAGY 1<<30
#define KICSI 1e-12
#define P pair<double,double>
#define x first
#define y second

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

P a={0,NAGY};
int n,k,i,j,bur,h;

bool fgv1(P r, P p)
{
    int f=0;

    double cr=(r.x-a.x)*(p.y-a.y)-(p.x-a.x)*(r.y-a.y);

    return cr>KICSI;
}

bool fgv(P q, P r, P p)
{
    int f=0;

    double cr=(r.x-q.x)*(p.y-q.y)-(p.x-q.x)*(r.y-q.y);

    return cr>KICSI;
}

int main()
{
    cin>>n;
    vector<P>x(n+1);

    for(i=1;i<=n;i++)
    {
        cin>>x[i].x>>x[i].y;
        if(x[i].y<a.y)
        {
            h=i;
            a=x[i];
        }
        else if(x[i].y==a.y && x[i].x<a.x)
        {
            h=i;
            a=x[i];
        }
    }

    x[h]=x[1];
    x[1]=a;

    sort(x.begin()+2,x.end(),fgv1);
    x.push_back(x[1]);

    vector<P>v(n+5);

    v[1]=x[1];
    v[2]=x[2];
    i=2;
    j=3;
    bur=2;

    for(i=3;i<=n+1;++i)
    {
        while(bur>2 && !fgv(v[bur-1],v[bur],x[i])) --bur;

        ++bur;
        v[bur]=x[i];
    }
    cout<<bur-1<<"\n";
    for(i=1;i<bur;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}