Cod sursa(job #2421356)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 mai 2019 20:55:34
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define EPS 0.000000000001
#define NMAX 120005
using namespace std;

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

int poz = 3;

struct punct
{
    double x, y, unghi;
} v[NMAX], st[NMAX];

double getUnghi(double x, double y)
{
    double ung = 0;
    if(x < 0)
        ung = 90.0 + atan2(x, y) * 180 / M_PI;
    else ung = 90.0 - atan2(x, y) * 180 / M_PI;
    return ung;
}

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

int main()
{
    int n;
    fin >> n;

    for(int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, [](punct a, punct b)
    {
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    for(int i = 2; i <= n; ++i){
        v[i].x -= v[1].x, v[i].y -= v[1].y;
        v[i].unghi = getUnghi(v[i].x, v[i].y);
    }
    sort(v + 2, v + n + 1, [](punct a, punct b)
    {
        if(abs(a.unghi - b.unghi) < EPS)
            return a.y < b.y;
        return a.unghi < b.unghi;
    });

    st[1].x = 0, st[1].y = 0;
    st[2] = v[2], st[3] = v[3];
    for(int i = 4; i <= n; ++i){
        while(poz > 1 && det(st[poz - 1], st[poz], v[i]) <= 0)
            --poz;
        st[++poz] = v[i];
    }

    fout << poz << '\n';
    for(int i = 1; i <= poz; ++i)
        fout << fixed << setprecision(6) << st[i].x + v[1].x << ' ' << st[i].y + v[1].y << '\n';
    return 0;
}