Cod sursa(job #3162095)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 28 octombrie 2023 12:52:26
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 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;
    }

    bool operator < (const Point &other) const
    {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
};

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 GetCadran(Point p1)
{
    if(p1.x >= 0 && p1.y >= 0)
        return 1;
    if(p1.x >= 0 && p1.y < 0)
        return 2;
    if(p1.x < 0 && p1.y < 0)
        return 3;
    return 4;
}

double Distance(Point p)
{
    return p.x * p.x + p.y * p.y;
}

bool cmpT(Point p1, Point p2)
{
    int cadran1 = GetCadran(p1);
    int cadran2 = GetCadran(p2);

    if(cadran1 != cadran2)
        return cadran1 < cadran2;

    double cross = CrossProduct({0, 0}, p1, p2);
    if(cross != 0)
        return cross > 0;
    
    return Distance(p1) < Distance(p2);
}

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();

    sort(points + 1, points + n + 1);

    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);
    }

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

    return 0;
}