Cod sursa(job #1608340)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 21 februarie 2016 23:53:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream ka("infasuratoare.in");
ofstream ki("infasuratoare.out");

const int N_MAX = 120000;

int n;

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

stack <Punct> coada;

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);
}

int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
        ka >> puncte[i].x >> puncte[i].y;
    sort(puncte + 1, puncte + n + 1);
    coada.push(puncte[1]);
    coada.push(puncte[2]);
    int curent = 2;
    while(curent < n)
    {
        coada.push(puncte[++curent]);
        Punct p1 = coada.top();
        coada.pop();
        Punct p2 = coada.top();
        coada.pop();
        Punct p3 = coada.top();
        coada.pop();
        while(!coada.empty() && cross_product(p3, p2, p1) <= 0)
        {
            p2 = p3;
            p3 = coada.top();
            coada.pop();
        }
        coada.push(p3);
        if(cross_product(p3, p2, p1) > 0)
            coada.push(p2);
        coada.push(p1);
    }
    int primele = coada.size();
    while(!coada.empty())
    {
        p_noi[coada.size()] = coada.top();
        coada.pop();
    }
    coada.push(puncte[1]);
    coada.push(puncte[2]);
    curent = 2;
    while(curent < n)
    {
        coada.push(puncte[++curent]);
        Punct p1 = coada.top();
        coada.pop();
        Punct p2 = coada.top();
        coada.pop();
        Punct p3 = coada.top();
        coada.pop();
        while(!coada.empty() && cross_product(p3, p2, p1) >= 0)
        {
            p2 = p3;
            p3 = coada.top();
            coada.pop();
        }
        coada.push(p3);
        if(cross_product(p3, p2, p1) < 0)
            coada.push(p2);
        coada.push(p1);
    }
    coada.pop();
    while(!coada.empty())
    {
        p_noi[++primele] = coada.top();
        coada.pop();
    }
    primele--;
    ki << primele << '\n';
    for(int i = 1; i <= primele; i++)
        ki << fixed << setprecision(9) << p_noi[i].x << " " << p_noi[i].y << '\n';
}