Cod sursa(job #1822116)

Utilizator Y0da1NUME JMECHER Y0da1 Data 4 decembrie 2016 12:27:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

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

class punct{
public:
    double x;
    double y;
    bool operator < (const punct & p)
    {
        if(x < p.x)
            return 1;
        else if (x > p.x)
            return 0;
        if(y<p.y) //daca au abscisele egale sortam dupa y
            return 1;
        return 0;
    }
};
int n;
punct v[121000], stiva[121000];
int vf;
double prod_vectorial(const punct &A, const punct &B, const punct &C)
{
    double rez = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);  //cu + e la stanga, cu - e la dreapta
    return rez;
}
int cmp (const punct & p1,const punct & p2)
{
    int rez = prod_vectorial(v[0], p1, p2) < 0;
    return rez;
}
int main()
{
    int i;
    in>>n;
    for(i=0;i<n;++i)
        in>>v[i].x>>v[i].y;
    int pos = 0;
    for (i=1;i<n;++i)
        if (v[i] < v[pos])
            pos=i;              //gasim punctul cel mai "stanga-jos"
    swap(v[0], v[pos]);
    sort(v + 1, v + n, cmp);
    ///graham propriu-zis

    stiva[0] = v[0];
    stiva[1] = v[1];
    vf = 1;
    for (int i = 2; i < n; ++i)
    {
        while (vf >= 1 && prod_vectorial(stiva[vf - 1], stiva[vf], v[i]) > 0)
            --vf;
        ++vf;
        stiva[vf] = v[i];
    }
    //afisam in ordine inversa ca se cere ordine trigo
    out<< fixed;
    out<< vf+1 << "\n";
    for (int i = vf; i >= 0; --i)
        out << setprecision(9) << stiva[i].x << " " << stiva[i].y << "\n";
    in.close();
    out.close();
    return 0;
}