Cod sursa(job #2575335)

Utilizator FrostfireMagirescu Tudor Frostfire Data 6 martie 2020 12:58:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 2000000000
#define NMAX 120000

using namespace std;

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

int n, p, vf;
pair <double, double> ll, v[NMAX+10], stiva[NMAX+10];

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

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

int main()
{
    f >> n;
    ll = make_pair(inf, inf);
    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], p = i;
        }

    for(int i=1; i<=n; i++) v[i].first -= ll.first, v[i].second -= ll.second;
    swap(v[1], v[p]);

    sort(v+2, v+n+1, mycmp);
    v[++n] = v[1];
    for(int i=1; i<=3; i++) stiva[++vf] = v[i];

    for(int i=4; i<=n; 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;
}