Cod sursa(job #1386871)

Utilizator Ionut228Ionut Calofir Ionut228 Data 13 martie 2015 13:54:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int N, top;

struct puncte
{
    double x, y;
};
puncte V[120005], ST[120005];

double cross_panta(puncte A, puncte B, puncte C)
{
    return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}

bool cmp(puncte p1, puncte p2)
{
    return cross_panta(V[1], p1, p2) < 0;
}

void sort_points()
{
    int pos = 1;
    for (int i = 2; i <= N; ++i)
        if (V[i].x < V[pos].x || (V[i].x == V[pos].x && V[i].y < V[pos].y))
            pos = i;
    swap(V[1], V[pos]);

    sort(V + 2, V + N + 1, cmp);
}

void convex_hull()
{
    sort_points();

    ST[1] = V[1];
    ST[2] = V[2];
    top = 2;

    for (int i = 3; i <= N; ++i)
    {
        while (top >= 2 && cross_panta(ST[top - 1], ST[top], V[i]) > 0)
            --top;
        ST[++top] = V[i];
    }
}

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

    convex_hull();

    fout << top << '\n';
    for (int i = 1; i <= top; ++i)
        fout << fixed << setprecision(12) << ST[i].x << ' ' << ST[i].y << '\n';

    fin.close();
    fout.close();
    return 0;
}