Cod sursa(job #1948686)

Utilizator medicinedoctoralexandru medicinedoctor Data 1 aprilie 2017 12:31:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 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;
} MinPt;

vector <pt> a, h;

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

    cin >> MinPt.x >> MinPt.y;
    a.push_back(MinPt);

    for (int i = 1; i < n; i++)
    {
        cin >> p.x >> p.y;
        a.push_back(p);
        if (p.x < MinPt.x || (p.x == MinPt.x && p.y < MinPt.y)) MinPt = p;
    }
    //cout << MinPt.x << ' ' << MinPt.y << '\n' << '\n' << '\n';
}

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 a, pt b)
{
    return det(MinPt, a, b) > 0;
}

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

    for (size_t i = 2; i < a.size(); i++)
    {
        h.push_back(a[i]);
        int q = h.size() - 1;
        while ( det(h[q - 2], h[q - 1], h[q]) < 0)
        {
            q = h.size() - 1;
            pt x = h[q];
            h.pop_back();
            h.back() = x;
        }
    }
    h.push_back(MinPt);
}

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

int main()
{
    read();

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

//    for (size_t i = 0; i < a.size(); i++)
//        cout << a[i].x << ' ' << a[i].y << '\n';
//    cout << '\n' << '\n' << '\n';

    ch();

    write();

    return 0;
}