Cod sursa(job #3288359)

Utilizator Tudor28Ceclan Tudor Tudor28 Data 21 martie 2025 18:30:13
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
#define oo 1000000000

struct punct
{
    double x, y;
} v[120005];

bool smaller(punct x, punct y)
{
    if (x.y < y.y)
        return true;
    if (x.y == y.y)
        return x.x < y.x;
    return false;
}

int orientation(punct a, punct b, punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

double angle(punct a, punct b)
{
    return atan2(b.y - a.y, b.x - a.x);
}

bool cmp(punct a, punct b)
{
    return angle(v[0], a) < angle(v[0], b);
}

int main()
{
    int n;
    fin >> n;
    punct start;
    int istart;

    start.x = oo;
    start.y = oo;

    for (int i = 0; i < n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if (smaller(v[i], start))
        {
            start = v[i];
            istart = i;
        }
    }

    swap(v[istart], v[0]);   // Swap the start point to the first position
    sort(v + 1, v + n, cmp); // Sort by angle relative to the start point

    vector<int> ras;
    ras.push_back(0); // Add the start point to the convex hull

    for (int i = 1; i < n; i++)
    {
        // Print for debugging the sorted points
        cout << "Checking point: (" << v[i].x << ", " << v[i].y << ")\n";

        // Backtrack if the turn is clockwise (orientation < 0)
        while (ras.size() > 2 && orientation(v[ras[ras.size() - 2]], v[ras[ras.size() - 1]], v[i]) < 0)
        {
            cout << "Popping point: (" << v[ras[ras.size() - 1]].x << ", " << v[ras[ras.size() - 1]].y << ")\n";
            ras.pop_back();
        }

        // Add current point to the convex hull
        ras.push_back(i);
    }

    // Output the number of points on the convex hull
    fout << ras.size() << '\n';

    // Output the points on the convex hull
    for (auto i : ras)
    {
        fout << v[i].x << " " << v[i].y << '\n';
    }

    return 0;
}