Cod sursa(job #3300882)

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

using namespace std;

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

#define MAX 1000000000.0

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

vector<POINT> points;
POINT origin = {MAX, MAX, 0.0};

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

bool compareFunction(POINT a, POINT b)
{
    if (a.angle == b.angle)
    {
        double distA = (a.x - origin.x) * (a.x - origin.x) + (a.y - origin.y) * (a.y - origin.y);
        double distB = (b.x - origin.x) * (b.x - origin.x) + (b.y - origin.y) * (b.y - origin.y);

        return (distA > distB);
    }

    return (a.angle < b.angle);
}

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

    return (product > 0);
}

bool isOrigin(POINT point)
{
    if (point.y < origin.y)
    {
        return true;
    }
    else if (point.y == origin.y)
    {
        if (point.x < origin.x)
        {
            return true;
        }
    }

    return false;
}

void processInput()
{
    int n;

    fin >> n;

    points.resize(n);

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

        fin >> X >> Y;

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

        if (isOrigin(points[i]))
        {
            origin = points[i];
        }
    }

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

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

    int j = 0;

    for (long unsigned int i = 1; i < points.size(); i++)
    {
        if (fabs(points[i].angle - points[j].angle) != 0)
        {
            points[++j] = points[i];
        }
    }

    points.resize(j + 1);
}

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

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++)
    {
        while (st.size() >= 2)
        {
            POINT current = st[st.size() - 1];

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

            POINT next = points[i];

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

        st.push_back(points[i]);
    }

    printResult(st);
}

int main()
{
    processInput();

    solve();

    return 0;
}