Cod sursa(job #2412690)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 22 aprilie 2019 14:39:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#define ld long double
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,j;
typedef pair<ld,ld> pct;
pct v[400000], ans[400000];
bool ver(pct a, pct b, pct c)
{
    return (a.x - c.x) * (b.y - c.y) < (a.y-c.y) * (b.x - c.x);
}
int main()
{
    f >> n;
    for(int i = 0; i < n; ++i)
        f >> v[i].x >> v[i].y;
    sort(v, v+n);
    reverse_copy(v ,v+n-1, v+n);
    for(int i = 0; i < 2 * n - 1; ans[j++] = v[i++])
            while(j > 1 && ver(ans[j-2], ans[j-1], v[i]) )
                j--;
    j--;
    g << j << '\n';
    g << setprecision(6) << fixed;
    for(int i = 0; i < j; ++i)
        g << ans[i].x << ' ' << ans[i].y << '\n';
    f.close();
    g.close();
    return 0;
}