Cod sursa(job #1990309)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 11 iunie 2017 13:17:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
    double x, y;
};
const int NMAX = 120021;
punct a[NMAX], O;
int N, M, s[NMAX];
double prod_vec(punct O, punct A, punct B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int cmp(punct A, punct B)
{
    return prod_vec(O, A, B) > 0;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int i, j;
    f >> N;
    f >> a[1].x >> a[1].y;
    O = a[1];
    j = 1;
    for (i = 2; i <= N; ++i)
    {
        f >> a[i].x >> a[i].y;
        if (a[i].y < O.y || (a[i].y == O.y && a[i].x < O.x))
            O = a[i], j = i;
    }
    swap(a[1], a[j]);
    sort(a + 2, a + N + 1, cmp);
    M = 2;
    s[1] = 1;
    s[2] = 2;
    for (i = 3; i <= N; ++i)
    {
        while (M >= 2 && prod_vec(a[s[M]], a[i], a[s[M - 1]]) <= 0) M--;
        s[++M] = i;
    }
    if (prod_vec(a[s[M]], O, a[s[M - 1]]) == 0) --M;
    g << M << '\n';
    for (i = 1; i <= M; ++i)
        g << fixed << setprecision(6) << a[s[i]].x << ' ' << a[s[i]].y << '\n';
    return 0;
}