Cod sursa(job #2081575)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 4 decembrie 2017 20:38:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define pdd pair<double, double>
#define x first
#define y second
const int Nmax = 1200000 + 5;
pdd p[Nmax];
int n, sol[Nmax], k;
bool cmp(pdd a1, pdd a2)
{
    if(a1.y == a2.y)return a1.x < a2.x;
    return a1.y < a2.y;
}
double det(int a, int b, int c)
{
    return (p[b].x - p[a].x) * (p[c].y - p[a].y) - (p[c].x - p[a].x) * (p[b].y - p[a].y);
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> p[i].x >> p[i].y;

    sort(p + 1, p + n + 1, cmp);

    sol[1] = 1; sol[2] = 2;
    k = 2;
    for(int i = 3; i <= n; ++i)
    {
        while(k > 1 && det(sol[k - 1], sol[k], i) < 0)
            k --;
        sol[++k] = i;
    }
    for(int i = n - 1; i >= 1; --i)
    {
        while(k > 1 && det(sol[k - 1], sol[k], i) < 0)
            k --;
        sol[++k] = i;
    }
    fout << k - 1 << '\n';
    for(int i = 1; i < k; ++i)
        fout << fixed << setprecision(12) << p[sol[i]].x << " " << p[sol[i]].y << '\n';
}