Cod sursa(job #870413)

Utilizator rodica_tomaRodica Toma rodica_toma Data 3 februarie 2013 13:08:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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;

inline double det(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);
}

inline int cmp(const Punct &A, const Punct &B)
{
    return det(P[1],A,B)<0;
}

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

    f>>N;
    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].x < O.x || (P[i].x == O.x && P[i].y < O.y))
        {
            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 >= 2 && det(P[st[varf - 1]], P[st[varf]],P[i]) >= 0)
            varf--;
        st[++varf] = i;
    }
    g<<fixed;
    g<<varf<<endl;
    g<<setprecision(9);
    g<<P[st[1]].x<<' '<<P[st[1]].y<<endl;
    for(int i = varf; i >=2; i--)
        g<<P[st[i]].x<<' '<<P[st[i]].y<<endl;
    g.close();
    return 0;
}