Cod sursa(job #3346513)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 14 martie 2026 09:21:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point{
    double x, y;
} v[120005];
vector<point> ans;

int det(point a, point b, point c)
{
    double d1 = (b.x - a.x) * (c.y - a.y);
    double d2 = (c.x - a.x) * (b.y - a.y);
    if(d1 == d2) return 0;
    return (d1 > d2 ? 1 : -1);
}

int cmp(point a, point b) {
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    int n; f >> n;
    for(int i = 1; i <= n; i++) f >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);

    for(int i = 1; i <= n; i++)
    {
        while(ans.size() >= 2 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
        ans.push_back(v[i]);
    }

    for(int i = n - 1; i >= 1; i--)
    {
        while(ans.size() >= 2 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0) ans.pop_back();
        ans.push_back(v[i]);
    }

    ans.pop_back();
    g << ans.size() << '\n';
    for(auto a : ans)
        g << setprecision(12) << fixed << a.x << " " << a.y << '\n';
    return 0;
}