Cod sursa(job #2539650)

Utilizator FrostfireMagirescu Tudor Frostfire Data 6 februarie 2020 09:21:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120000
#define inf 2000000000

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n, m, vf;
pair <double, double> v[NMAX+10], ll=make_pair(inf, inf), stiva[NMAX+10];

inline bool mycmp(pair <double, double> a, pair <double, double> b)
{   return (a.second * b.first < a.first * b.second);
}

int area(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{   double A = (a.first - b.first) * (a.second - c.second) - (a.second - b.second) * (a.first - c.first);
    if(A < 0) return -1;
    return 1;
}

int main()
{
    f >> n;
    for(int i=1; i<=n; i++)
        {   f >> v[i].first >> v[i].second;
            if(v[i].second < ll.second || (v[i].second == ll.second && v[i].first < ll.first)) ll = v[i];
        }
    for(int i=1; i<=n; i++)
        {   v[i].first -= ll.first;
            v[i].second -= ll.second;
            if(v[i].first != 0 || v[i].second != 0) v[++m] = v[i];
        }
    n = m;
    sort(v+1, v+n+1, mycmp);
    v[n+1] = v[1];
    stiva[++vf] = make_pair(0, 0);
    stiva[++vf] = v[1];
    stiva[++vf] = v[2];
    for(int i=3; i<=n+1; i++)
        {   while(vf > 2 && area(stiva[vf-2], stiva[vf-1], stiva[vf]) != area(stiva[vf-1], stiva[vf], v[i])) vf--;
            stiva[++vf] = v[i];
        }
    g << vf-1 << '\n';
    g << setprecision(6) << fixed;
    for(int i=1; i<vf; i++) g << stiva[i].first + ll.first << ' ' << stiva[i].second + ll.second << '\n';
    return 0;
}