Cod sursa(job #3148692)

Utilizator Raul_AArdelean Raul Raul_A Data 3 septembrie 2023 15:28:39
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define cin in
#define cout out
#define eb emplace_back
#define pii pair<double, double>
using namespace std;

const string file_name("infasuratoare");

ifstream in(file_name + ".in");
ofstream out(file_name + ".out");

struct date
{
    double x, y;
} v[150];

int n, vf, pos;
int s[150];
double xmin, ymin = DBL_MAX, x, y;

int convex(date a, date b, date c)
{
    double rez = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    return rez > 0;
}

int main()
{
    cout<<fixed<<setprecision(20);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
        if (ymin > v[i].y)
        {
            xmin = v[i].x;
            ymin = v[i].y;
            pos = i;
        }
    }

    for (int i = 1; i <= n; i++)
        v[i].x -= xmin,
            v[i].y -= ymin;

    swap(v[1], v[pos]);

    sort(v + 2, v + n + 1, [](date a, date b)
         { return a.x * b.y >= b.x * a.y; });

    s[1] = 1;
    s[2] = 2;
    vf = 2;

    for (int i = 3; i <= n; i++)
    {
        while (vf >= 3 and !convex(v[s[vf - 1]], v[s[vf]], v[i]))
            vf--;

        s[++vf] = i;
    }

    cout << vf << '\n';
    for (int i = 1; i <= vf; i++)
        cout << v[s[i]].x + xmin << ' ' << v[s[i]].y + ymin << '\n';

    return 0;
}