Cod sursa(job #3300872)

Utilizator florin977Docheru Florin-Andrei florin977 Data 19 iunie 2025 18:29:41
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 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;
POINT origin = {MAX, MAX, 0.0};

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)
{
    if (a.angle == b.angle)
    {
        float distA = (a.x - origin.x) * (a.x - origin.x) + (a.y - origin.y) * (a.y - origin.y);
        float 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)
{
    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;

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

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