Cod sursa(job #3300866)

Utilizator florin977Docheru Florin-Andrei florin977 Data 19 iunie 2025 18:01:09
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

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

#define MAX 1000000000.0

typedef struct
{
    float x, y, angle;
} POINT;

vector<POINT> points;

void printPoint(POINT point)
{
    fout << point.x << ' ' << point.y << '\n';
}

float computeAngle(POINT point, POINT origin)
{
    return atan2(point.y - origin.y, point.x - origin.x);
}

bool compareFunction(POINT a, POINT b)
{
    return (a.angle < b.angle);
}

bool isConvex(POINT prev, POINT current, POINT next)
{
    float product = (current.x - prev.x) * (next.y - prev.y) - (current.y - prev.y) * (next.x - prev.x);

    return (product >= 0);
}

void processInput()
{
    int n;

    POINT origin = {MAX, MAX, 0.0};

    fin >> n;

    points.resize(n);

    for (int i = 0; i < n; i++)
    {
        float X, Y;

        fin >> X >> Y;

        points[i] = {X, Y, 0.0};

        if (points[i].y < origin.y)
        {
            origin = points[i];
        }
        else if (points[i].y == origin.y)
        {
            if (points[i].x < origin.x)
            {
                origin = points[i];
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        points[i].angle = computeAngle(points[i], origin);
    }

    for (int i = 0; i < n; i++)
    {
        points[i].angle = computeAngle(points[i], origin);
    }

    sort(points.begin(), points.end(), compareFunction);
}

void printResult(vector<POINT>& st)
{
    fout << st.size() << '\n';

    for (long unsigned int i = 0; i < st.size(); i++)
    {
        printPoint(st[i]);
    }
}

void solve()
{
    vector<POINT> st;

    st.push_back(points[0]);
    
    if (points.size() > 1)
    {
        st.push_back(points[1]);
    }

    for (long unsigned int i = 2; i < points.size(); i++)
    {
        POINT current = st[st.size() - 1];

        POINT prev = st[st.size() - 2];

        POINT next = points[i];

        if (!isConvex(prev, current, next))
        {
            st.pop_back();
        }

        st.push_back(next);
    }

    printResult(st);
}

int main()
{
    processInput();

    solve();
    
    return 0;
}