Cod sursa(job #2848468)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 12 februarie 2022 17:20:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
#include <bits/stdc++.h>

using namespace std;

/*******************************/
// INPUT / OUTPUT
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N;

struct Point
{
    long double x, y;
} p0;

stack <int> s;
vector <int> ans;
vector <Point> points;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N;

    long double x, y;
    for (int i = 0 ; i < N ; ++ i)
    {
        f >> x >> y;
        points.push_back({x, y});
    }
}
///-------------------------------------
int Orientation(const Point &p0, const Point &p1, const Point &p2)
{
    long double val = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y);

    if (val == 0) return 0; // collinear

    if (val > 0) return 1; // clockwise
    return -1; // counter-clockwise
}
///-------------------------------------
long double DistSqrd(const Point &p1, const Point &p2)
{
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
///-------------------------------------
bool comp(const Point &p1, const Point &p2)
{
    int o = Orientation(p0, p1, p2);

    if (o == 0) // Points are collinear
    {
        return DistSqrd(p0, p1) <= DistSqrd(p0, p2);
    }

    if (o == 1) return 0;
    return 1;
}
///-------------------------------------
Point SecondInStack()
{
    int top = s.top();
    s.pop();
    int idx = s.top();
    s.push(top);
    return points[idx];
}
///-------------------------------------
inline void Solution()
{
    long double minY = points[0].y, minPoint = 0;

    for (int i = 1 ; i < N ; ++ i)
    {
        if ((points[i].y < minY) || (points[i].y == minY && points[i].x < points[minPoint].x))
        {
            minY = points[i].y;
            minPoint = i;
        }
    }

    swap(points[0], points[minPoint]);
    p0 = points[0];
    
    sort(points.begin() + 1, points.end(), comp);

    s.push(0);
    s.push(1);

    for (int i = 2 ; i < N ; ++ i)
    {
        while (s.size() > 1 && Orientation(SecondInStack(), points[s.top()], points[i]) != -1)
        {
            s.pop();
        }
        s.push(i);
    }

    while (!s.empty())
    {
        int top = s.top();
        s.pop();
        ans.push_back(top);
    }
    reverse(ans.begin(), ans.end());
}
///-------------------------------------
inline void Output()
{
    for (auto idx: ans)
    {
        g << fixed << setprecision(12) << points[idx].x << " " << points[idx].y << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}