Cod sursa(job #1331702)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 31 ianuarie 2015 23:56:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream ka("infasuratoare.in");
ofstream ki("infasuratoare.out");

const int N_MAX = 120000;

int n, nr;

struct punct
{
    double x, y;
    bool operator < (const punct arg) const
    {
        if(y == arg.y)
            return x < arg.x;
        else
            return y < arg.y;
    }
}puncte[N_MAX + 1], raspuns[N_MAX + 1];

double cross_product(punct a, punct b, punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool comp(punct a, punct b)
{
    return cross_product(puncte[1], a, b) < 0;
}

void sortare()
{
    int poz = 1;
    for(int i = 1; i <= n; i++)
        if(puncte[i] < puncte[poz])
            poz = i;
    swap(puncte[1], puncte[poz]);
    sort(puncte + 2, puncte + n + 1, comp);
}

int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
        ka >> puncte[i].x >> puncte[i].y;
    sortare();

    raspuns[1] = puncte[1];
    raspuns[2] = puncte[2];
    nr = 2;
    for (int i = 3; i <= n; ++i)
    {
        while (nr >= 2 && cross_product(raspuns[nr - 1], raspuns[nr], puncte[i]) > 0)
            nr--;
        raspuns[++nr] = puncte[i];
    }
    ki << fixed;
    ki << nr << '\n';
    for (int i = nr; i >= 1; i--)
        ki << setprecision(9) << raspuns[i].x << " " << raspuns[i].y << '\n';
}