Cod sursa(job #870287)

Utilizator rodica_tomaRodica Toma rodica_toma Data 3 februarie 2013 08:14:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include<fstream>
#include<iomanip>
#include <algorithm>

using namespace std;

#define MAXN 120050
int N;
struct Punct {
    double x, y;
};

Punct P[MAXN];
Punct O;
int st[MAXN];
int varf;

double crossProduct(const Punct &A, const Punct &B, const Punct &C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

//conditia corecta (cand sunt ordonate)
inline int cmp(const Punct &A, const Punct &B)
{
    return (A.y < B.y || (A.y == B.y && A.x < B.x));
}

int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int poz;

    f>>N;
    f>>setprecision(12)>>fixed;
    f>>P[1].x>>P[1].y;
    O=P[1];
    poz=1;
    for(int i = 2; i <= N; i++)
    {
        f>>P[i].x>>P[i].y;
        if(P[i].y < O.y || (P[i].y == O.y && P[i].x < O.x))
        {
            O=P[i];
            poz=i;
        }
    }
    O=P[poz];
    P[poz]=P[1];
    P[1]=O;

    sort(P+2, P + N+1, cmp);

    st[1] = 1;
    st[2] = 2;

   varf = 2;

   for(int i = 3; i<=N; i++)
   {
        while(varf >= 1 && crossProduct(P[st[varf - 1]], P[i], P[st[varf]]) > 0)
            varf--;
        st[++varf] = i;
    }

    g<<varf<<endl;
    g<<setprecision(12)<<fixed;
    for(int i = 1; i <= varf; i++)
        g<<P[st[i]].x<<' '<<P[st[i]].y<<endl;
    g.close();
    return 0;
}