Cod sursa(job #947382)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 7 mai 2013 11:46:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define Nmax 120005
#define PD pair<double, double>
#define mp make_pair
#define x first
#define y second

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

PD V[Nmax], St[Nmax], Convex[Nmax];
int N, K;

double det(PD A, PD B, PD C)
{
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

void Add_Points()
{
    int Stsize = 0;
    St[Stsize ++] = V[1];
    St[Stsize ++] = V[2];
    for(int i = 3; i <= N; ++ i)
    {
        while(Stsize >= 2 && det(St[Stsize - 2], St[Stsize - 1], V[i]) < 0) Stsize --;
        St[Stsize ++] = V[i];
    }
    for(int i = 0; i < Stsize - 1; ++ i) Convex[++ K] = St[i];
}

int main()
{
    f>>N;
    for (int i=1; i<=N; ++i) f>>V[i].x>>V[i].y;

    sort(V + 1, V + N + 1);
    Add_Points();
    reverse(V + 1, V + N + 1);
    Add_Points();

    g<<K<<'\n';
    for (int i=1; i<=K; i++) g<<fixed<<setprecision(8)<<Convex[i].x<<' '<<Convex[i].y<<'\n';

    f.close(); g.close();
    return 0;
}