Cod sursa(job #3139125)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 25 iunie 2023 15:33:42
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;
// #define double float

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
 
const int INF = (1 << 30);
 
// ifstream cin("intersectiesegmente.in");
// ofstream cout("intersectiesegmente.out");

struct Point
{
    double x, y;
    void Read()
    {
        cin >> x >> y;
    }
    Point operator - (const Point& other) const
    {
        return { x - other.x, y - other.y };
    }
    double operator * (const Point& other) const
    {
        return x * other.y - y * other.x;
    }
};

const int NMAX = 120000;

int n;
Point a[NMAX + 1];
Point st[NMAX + 1];
int ind;
int leftmost;

bool cmp(Point x, Point y)
{
    return (x - a[1]) * (y - a[1]) < 0;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        a[i].Read();

    leftmost = 1;
    for(int i = 2; i <= n; i++)
        if(make_pair(a[i].x, a[i].y) < make_pair(a[leftmost].x, a[leftmost].y))
            leftmost = i;

    swap(a[1], a[leftmost]);
    sort(a + 2, a + n + 1, cmp);
    st[++ind] = a[1];
    st[++ind] = a[2];
    for(int i = 3; i <= n; i++)
    {
        while(ind >= 2 && (st[ind] - st[ind - 1]) * (a[i] - st[ind - 1]) > 0)
            ind--;
        st[++ind] = a[i];
    }

    cout << ind << '\n';
    for(int i = ind; i >= 1; i--)
        cout << fixed << setprecision(9) << a[i].x << ' ' << a[i].y << '\n';

    
    return 0;
}