Cod sursa(job #3375772)

Utilizator Alias47John Doe Alias47 Data 13 noiembrie 2026 16:13:13
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
string file = "infasuratoare";
ifstream f(file + ".in");
ofstream g(file + ".out");

int n;
long double x, y;
struct pct
{
    long double x, y;
    friend bool operator<(pct a, pct b)
    {
        if (a.x < b.x)
            return 1;
        if (a.x == b.x && a.y < b.y)
            return 1;
        return 0;
    }
    void output()
    {
        g << fixed << setprecision(6) << x << ' ' << y << '\n';
    }
    void output_desmos()
    {
        g << '(' << (int)x << ',' << (int)y << ')' << endl;
    }
};
vector<pct> v, ans;
pct p0;

int ccw(pct p, pct p1, pct p2)
{
    return (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x);
}
bool cmp(pct a, pct b)
{
    return ccw(p0, a, b) > 0; //smaller if to the right
}
void polar_sort(vector<pct>& v)
{
    //find point with smallest x (and y if multiple exist)
    int minpos = 1;
    for (int i = 2; i <= n; i++)
    {
        if (v[i] < v[minpos])
            minpos = i;
    }
    swap(v[1], v[minpos]);
    p0 = v[1];
    //sort by ccw
    sort(v.begin() + 2, v.end(), cmp);
}
void test()
{
    for (pct i : v)
        i.output_desmos();
    g << endl;
}
void convex_hull(vector<pct>& stk)
{
    polar_sort(v);
    //test();
    stk.push_back(v[1]); //always in the convex hull
    stk.push_back(v[2]);
    for (int i = 3; i <= n; i++)
    { //right turn = get rid of the point in the middle of the 3
        while (stk.size() > 1 && ccw(v[i], stk.end()[-2], stk.end()[-1]) < 0) //no 0
        {
            stk.pop_back();
        }
        stk.push_back(v[i]);
    }
}

int main()
{
    f >> n;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
    }
    convex_hull(ans);
    g << ans.size() << endl;
    for (pct i : ans)
    {
        i.output();
    }
}