Cod sursa(job #3272585)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 30 ianuarie 2025 00:54:32
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nl '\n'

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 120005;

int n, ind = 1;

struct Point
{
    double x, y;
};
Point points[NMAX], st[NMAX];

double det(const Point& A, const Point& B, const Point& C)
{
    return (A.x-B.x)*(B.y-C.y)-(A.y-B.y)*(B.x-C.x);
}

bool cmp(const Point& A, const Point& B)
{
    return det(points[1], A, B) > 0;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        double x, y;
        fin >> x >> y;
        points[i] = {x, y};
        if ((points[i].x < points[ind].x) || (points[i].x == points[ind].x && points[i].y < points[ind].y))
            ind = i;
    }
    swap(points[1], points[ind]);
    sort(points+2, points+1+n, cmp);
    st[1] = points[1];
    st[2] = points[2];
    int m = 2;
    for (int i = 3; i <= n; i++)
    {
        while (m >= 2 && det(st[m-1], st[m], points[i]) < 0)
            m--;
        st[++m] = points[i];
    }
    fout << m << nl;
    fout << fixed << setprecision(6);
    for (int i = 1; i <= m; i++)
        fout << st[i].x << ' ' << st[i].y << nl;
    return 0;
}