Cod sursa(job #1885579)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 20 februarie 2017 08:40:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MAXN 120050

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct coord
{
    double x, y;
    bool operator<(const coord &e) const
    {
        if (x != e.x)
            return x < e.x;
        return y < e.y;
    }
};
coord a[MAXN];
int n;

void read()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
}

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

void add(vector<coord> &v, coord c)
{
    while (v.size() >= 2 && det(v[v.size()-2], v.back(), c) < 0)
        v.pop_back();
    v.push_back(c);
}

vector<coord> cap, coada;
void solve()
{
    sort(a+1, a+n+1);
    for (int i = 1; i <= n; i++)
        add(cap, a[i]);
    for (int i = n-1; i >= 1; i--)
        add(cap, a[i]);
    cap.pop_back();
}

int main()
{

    std::ios::sync_with_stdio(false);

    read();
    solve();
    fout << cap.size() << "\n";
    for_each(cap.begin(), cap.end(), [](coord &p){fout << p.x << " " << p.y << "\n";});


    return 0;
}