Cod sursa(job #3162085)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 28 octombrie 2023 12:39:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <cmath>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

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

const int NMAX = 12e4;

struct Point
{
    double x, y;
    void Read()
    {
        cin >> x >> y;
    }
};

int n;
Point points[NMAX + 1];
Point stack[NMAX + 1];
int stackIndex;

double CrossProduct(Point p1, Point p2, Point p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

void Reverse(Point a[])
{
    for(int i = 1, j = n; i < j; i++, j--)
        swap(a[i], a[j]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        points[i].Read();

    int bound = 2;
    for(int rep = 0; rep < 2; rep++)
    {
        for(int i = 1; i <= n; i++)
        {
            while(stackIndex >= bound && CrossProduct(stack[stackIndex - 1], stack[stackIndex], points[i]) < 0)
                stackIndex--;
            stack[++stackIndex] = points[i];
        }
        stackIndex--;
        bound += stackIndex;
        Reverse(points);
    }

    for(int i = 1; i <= stackIndex; i++)
        cout << stack[i].x << ' ' << stack[i].y << '\n';

    return 0;
}