Cod sursa(job #3266260)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 6 ianuarie 2025 22:05:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct point
{
    double x;
    double y;
};

point p[120001];

vector<point> stiva;

int n;

int cross_prod(point a, point b, point c)
{
    double area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (area < 0)
    {
        return -1; /// CA is turned clockwise over BA
    }
    else if (area == 0)
    {
        return 0; /// CA is colinear with BA
    }
    else if (area > 0)
    {
        return 1; /// CA is turned counter clockwise over BA
        /// this is what we need here
    }
}

bool cmp(point a, point b)
{
    return cross_prod(p[1], a, b) > 0;
}

void convex_hull()
{
    int minpos = 1;
    for (int i = 1; i <= n; i ++)
    {
        if (p[minpos].y > p[i].y)
        {
            minpos = i;
        }
        else if (p[minpos].y == p[i].y)
        {
            if (p[minpos].x > p[i].x)
            {
                minpos = i;
            }
        }
    }
    swap(p[minpos], p[1]);
    sort(p + 2, p + n + 1, cmp);
//    for (int i = 1; i <= n; i ++)
//    {
//        cout << p[i].x << " " << p[i].y << "\n";
//    }
    int top = 0;
    stiva.push_back(p[1]);
    stiva.push_back(p[2]);
    top ++;
    for (int i = 3; i <= n; i ++)
    {
        if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
        {
            top ++;
            stiva.push_back(p[i]);
        }
        else
        {
            while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
            {
                top --;
                stiva.pop_back();
            }
            top ++;
            stiva.push_back(p[i]);
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
    }
    convex_hull();
    cout << stiva.size() << "\n";
    cout << fixed;
    for (int i = 0; i < stiva.size(); i ++)
    {
        cout << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
    }
    return 0;
}