Cod sursa(job #2987637)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 2 martie 2023 17:25:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point
{
    double x, y;
};
int n;
vector<point> points;
vector<point> s1, s2;
vector<point> rez;

int orientation(point a, point b, point c)
{
    double v = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (v < 0)
    {
        return -1;
    }
    if (v > 0)
    {
        return 1;
    }
    return 0;
}

bool cw(point a, point b, point c, bool include_collinear)
{
    int o = orientation(a, b, c);
    return o < 0 || (o == 0 && include_collinear);
}

bool ccw(point a, point b, point c, bool include_collinear)
{
    int o = orientation(a, b, c);
    return o > 0 || (o == 0 && include_collinear);
}

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

void convex_hull(bool include_collinear = false)
{
    sort(points.begin(), points.end(), cmp);
    point p0 = points[0];
    s1.push_back(p0);
    for (int i = 1; i < (int)points.size(); i++)
    {
        while (s1.size() >= 2 && !ccw(s1[s1.size() - 2], s1.back(), points[i], include_collinear))
        {
            s1.pop_back();
        }
        s1.push_back(points[i]);
    }
    s2.push_back(p0);
    for (int i = 1; i < (int)points.size(); i++)
    {
        while (s2.size() >= 2 && !cw(s2[s2.size() - 2], s2.back(), points[i], include_collinear))
        {
            s2.pop_back();
        }
        s2.push_back(points[i]);
    }
    if (include_collinear && s1.size() == points.size())
    {
        reverse(s1.begin(), s1.end());
        rez = s1;
        return;
    }
    s2.pop_back();
    reverse(s2.begin(), s2.end());
    s2.pop_back();
    for (auto point : s1)
    {
        rez.push_back(point);
    }
    for (auto point : s2)
    {
        rez.push_back(point);
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        double x, y;
        fin >> x >> y;
        points.push_back({x, y});
    }
    convex_hull();
    fout << rez.size() << '\n';
    for (auto point : rez)
    {
        fout << fixed << setprecision(6) << point.x << ' ' << point.y << '\n';
    }
    return 0;
}