Cod sursa(job #2364167)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 3 martie 2019 21:49:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define nmax 120000
#define pdd pair<double,double>
#define x first
#define y second

using namespace std;

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

int n, mn;
pdd v[nmax + 5], s[nmax + 5];

double det(pdd A, pdd B, pdd C)
{
    return A.x * B.y + B.x * C.y + C.x * A.y - C.y * A.x - B.y * C.x - A.y * B.x;
}

bool comp(pdd A, pdd B)
{
    return det(A, B, v[1]) >= 0;
}

int main()
{
    in >> n;
    v[0] = {1e9+1, 0};
    for (int i = 1; i <= n; ++i)
    {
        in >> v[i].x >> v[i].y;
        if (v[i].x < v[mn].x || v[i].x == v[mn].x && v[i].y < v[mn].y)
            mn = i;
    }
    swap(v[mn], v[1]);
    sort(v + 2, v + 1 + n, comp);
    int last = 2;
    s[1] = v[1];
    s[2] = v[2];
    for (int i = 3; i <= n; ++i)
    {
        while (last >= 2 && det(s[last - 1], s[last], v[i]) < 0)
            --last;
        s[++last] = v[i];
    }
    out << last << '\n';
    out << fixed << setprecision(12);
    for (int i = 1; i <= last; ++i)
        out << s[i].x << " " << s[i].y << '\n';
    return 0;
}