Cod sursa(job #1948840)

Utilizator medicinedoctoralexandru medicinedoctor Data 1 aprilie 2017 14:20:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin ("infasuratoare.in" );
ofstream cout("infasuratoare.out");

struct pt
{
    double x, y;
};

vector <pt> a, h;

void read()
{
    int n;
    pt p;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> p.x >> p.y;
        a.push_back(p);
        if (p.x < a[0].x || (p.x == a[0].x && p.y < a[0].y)) swap(a[i], a[0]);
    }
}

double det(pt a, pt b, pt c)
{
    return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}

bool f_4_compare(pt x, pt y)
{
    return det(a[0], x, y) < 0;
}

void ch()
{
    h.push_back(a[0]);
    h.push_back(a[1]);

    for (size_t i = 2; i < a.size(); i++)
    {
        int q = h.size() - 1;
        while (h.size() > 1 && det(h[q - 1], h[q], a[i]) > 0)
            h.pop_back(), q = h.size() - 1;

        h.push_back(a[i]);
    }
}

void write()
{
    cout << h.size() ;
    cout << fixed;
    for (size_t i = 0; i < h.size(); i++)
        cout << setprecision(13) << '\n' << h[i].x << ' ' << h[i].y;
}

int main()
{
    read();

    sort(a.begin() + 1, a.end(), f_4_compare);

    ch();

    reverse(h.begin(), h.end());

    write();

    return 0;
}