Cod sursa(job #2854338)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 21 februarie 2022 11:30:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <bits/stdc++.h>

using namespace std;

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

int N;
int nr = 2;

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

vector <Point> points, ans;
/*******************************/
/// 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;
}
///-------------------------------------
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);

    ans.push_back(p0);
    ans.push_back(points[1]);   

    for (int i = 2 ; i < N ; ++ i)
    {
        while (nr > 1 && Orientation(ans[nr - 1], ans[nr - 2], points[i]) != 1)
        {
            ans.pop_back();
            nr --;
        }
        ans.push_back(points[i]);
        nr ++;
    }
}
///-------------------------------------
inline void Output()
{
    g << nr << "\n";
    for (int i = 0 ; i < nr ; ++ i)
    {
        g << fixed << setprecision(6) << ans[i].x << " " << ans[i].y << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}