Cod sursa(job #1131484)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 28 februarie 2014 20:28:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
//Convex Hull - O(NlogN) - with CrossProduct
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define Precizie 1000000
#define eps 0.0000001
#define Nmax 120099
using namespace std;
ifstream f("infasuratoare.in");

int N,k;
struct point {double x,y;}P[Nmax],st[Nmax],G;

inline void ReadInput(),PrintOutPut();
inline bool Equal(double x,double y),LessThan(double x,double y);

inline 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 cmp
{
    bool operator()(const point &A,const point &B)const
    {
        return atan2(A.y-G.y,A.x-G.x)<atan2(B.y-G.y,B.x-G.x);
    };
};

inline void ConvexHull()
{
    sort( P+2, P+1+N , cmp() ); // sortez in raport cu primul punct
    st[1]=P[1],st[2]=P[2];
    k=2;
    for(int i=3;i<=N;++i)
    {
        while(k>=2 && CrossProduct(st[k-1],st[k],P[i])<0)--k;
        st[++k]=P[i];
    }
}



int main()
{
    freopen("infasuratoare.out","w",stdout);
    ReadInput();
    ConvexHull();
    PrintOutPut();
    return 0;
}

inline bool Equal(double x,double y)
{
    if(fabs(x-y)<eps)return 1;
    else return 0;
}

inline bool LessThan(double x,double y)
{
    if(1LL*Precizie*x<1LL*Precizie*y)return 1;
    else return 0;
}

void ReadInput()
{
    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;
        G.x+=P[i].x;
        G.y+=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;
    }
    G.x=1.0*G.x/N;
    G.y=1.0*G.y/N;
    swap(P[1],P[j]);
}

void PrintOutPut()
{
    //solutia a fost generata in ordine trigonometrica
    printf("%d\n",k);
    for(int i=1;i<=k;++i)printf("%0.6f %0.6f\n",st[i].x,st[i].y);
}