Cod sursa(job #3214825)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 14 martie 2024 14:48:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>

#define double long double

using namespace std;

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

const int N = 12e4;
int s[N + 1];

int n;

struct point
{
    double x, y;

} a[N + 1], saved;

int det (point a, point b, point c)
{
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0);
}

bool operator < (const point &a, const point &b)
{
    return det (saved, a, b);
}

int main()
{
    cin >> n;
    cin >> 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[i], a[0]);
    }
    saved = a[0];
    a[n] = a[0];
    sort (a + 1, a + n);
    int len = 0, i = 2;
    s[len] = 0;
    s[++len] = 1;
    while (i <= n)
    {
        if (det (a[s[len - 1]], a[s[len]], a[i]) > 0)
            s[++len] = i++;
        else
            --len;
    }
    cout << len << '\n';
    for (int i = 0; i < len; ++i)
        cout << fixed << setprecision(12) << a[s[i]].x << ' ' << fixed << setprecision(12) << a[s[i]].y << '\n';
    return 0;
}