Cod sursa(job #2421385)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 mai 2019 21:35:27
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

#define double long double
#define EPS 1e-12
#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(y < 0)
        cout << x << ' ' << y << '\n';
    ung = atan2(y, x) * 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.y == b.y)
            return a.x < b.x;
        return a.y < b.y;
    });

    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];
    poz = 2;
    for(int i = 3; i <= n; ++i){
        while(poz > 1 && det(st[poz - 1], st[poz], v[i]) <= EPS)
            --poz;
        st[++poz] = v[i];
    }
    while(poz > 1 && det(st[poz - 1], st[poz], st[1]) <= EPS)
        --poz;

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