Cod sursa(job #2897236)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 3 mai 2022 08:42:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>

using namespace std;

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

const int N = 12e4;
int h[N + 2];

struct da
{
    double x, y;
} a[N + 2];

int ccw (da a, da b, da c)
{
    double ga = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
    if (ga == 0)
        return 0;
    if (ga > 0)
        return 1;
    return  -1;
}

bool cmp (da b, da c)
{
    return ccw(a[0], b, c) > 0;
}

int n;

int main()
{
    cin >> n >> a[0].x >> a[0].y;
    for (int i = 1; i < n; ++i)
    {
        cin >> a[i].x >> a[i].y;
        if (a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x))
            swap(a[0], a[i]);
    }
    sort (a + 1, a + n, cmp);
    a[n] = a[0];
    int i = 2, top = 1;
    h[0] = 0;
    h[1] = 1;
    while (i <= n)
    {
        if (ccw(a[h[top - 1]], a[h[top]], a[i]) > 0)
        {
            h[++top] = i;
            ++i;
        }
        else
            --top;
    }
    cout << top << '\n';
    for (int i = 0; i < top; ++i)
    {
        cout << fixed << setprecision(6) << a[h[i]].x << ' ' << fixed << setprecision(7) << a[h[i]].y << '\n';
    }
    return 0;
}