Cod sursa(job #870539)

Utilizator costi_.-.Costinnel costi_.-. Data 3 februarie 2013 16:07:34
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#define nmax 12001
#define eps 1e-12
using namespace std;

struct punct{
    double x,y;
};

punct P[nmax],HULL[nmax],LH[nmax],UH[nmax];
int N,NH,NLH,NUH;

double delta(punct &p1,punct &p2,punct &p3)
{
    return(
           p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y);
}

inline bool cmp(punct p1,punct p2)
{
    if(fabs(p1.x-p2.x)<=eps)
     if(p1.y<p2.y)
       return true;
       else
       return false;
    else
    if(p1.x<p2.x)
    return true;
    else
    return false;
}

void MonotoneChain()
{
    sort(P+1,P+N+1,cmp);

    int i;

    for(i=1;i<=N;i++)
    {
        while(NLH>=2 && delta(LH[NLH-1],LH[NLH],P[i])<=0.f)
        --NLH;

        LH[++NLH]=P[i];
    }

    for(i=N;i>=1;i--)
    {
        while(NUH>=2 && delta(UH[NUH-1],UH[NUH],P[i])<=0.f)
        --NUH;

        UH[++NUH]=P[i];
    }

    --NLH;
    --NUH;
    for(i=1;i<=NLH;i++)
    HULL[i]=LH[i];
    for(i=1;i<=NUH;i++)
    HULL[i+NLH]=UH[i];
    NH=NLH+NUH;
}

void citeste()
{
    ifstream f("infasuratoare.in");
    int i;

    f>>N;
    for(i=1;i<=N;i++)
    f>>P[i].x>>P[i].y;

    f.close();
}

void scrie()
{
    ofstream g("infasuratoare.out");
    int i;

    g<<NH<<'\n';
    for(i=1;i<=NH;i++)
    g<<HULL[i].x<<' '<<HULL[i].y<<'\n';

    g.close();
}

int main()
{
    //cout << "Hello world!" << endl;
    citeste();
    MonotoneChain();
    scrie();
    return 0;
}