Cod sursa(job #1420611)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 18 aprilie 2015 19:26:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
//Convex Hull - O(NlogN)
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define Precizie 1000000000000LL
#define eps 0.0000000000001
#define Nmax 120009
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
 
int N,k;
struct point {double x,y;}P[Nmax],st[Nmax];
 
bool Equal(const double& x, const double& y) {
  return fabs(x-y) < eps;
}

bool LessThan(const double& x, const double& y){
  return 1LL * Precizie * x < 1LL * Precizie * y;
}


double CrossProduct(point A, point B, point C){
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
};

struct cmpTrigonometric
{
    bool operator()(point A, point B)
    {
        return LessThan(0,CrossProduct(P[1],A,B));
    };
};
 
inline void ConvexHull()
{
    sort( P+2, P+1+N , cmpTrigonometric() ); // sortez in raport cu primul punct
    
    k = 2;
    st[1] = P[1];
    st[2] = P[2];
    for(int i = 3; i <= N; ++i) {
        while(k>=2 && LessThan(CrossProduct(st[k-1],st[k],P[i]),0))--k;
        st[++k]=P[i];
    }
}
 
int main()
{
    int j=1; // j va fi unde gasesc punctul cu ymin (xmin)
    f>>N;
    f>>P[1].x>>P[1].y;
    for(int i=2;i<=N;++i)
    {
        f>>P[i].x>>P[i].y;
        if(LessThan(P[i].y,P[j].y))j=i;
            else if(Equal(P[i].y,P[j].y) && LessThan(P[i].x,P[j].x))j=i;
    }
    swap(P[1],P[j]);
    ConvexHull();
    //solutia a fost generata in ordine trigonometrica
    g<<k<<'\n';
    g.precision(6);
    for(int i=1;i<=k;++i)
        g<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
    f.close();g.close();
    return 0;
}