Cod sursa(job #3225638)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 18 aprilie 2024 12:10:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define double long double
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const double EPS = 1e-7;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N;

struct Punct
{
    double x, y;
} p0;

vector <Punct> puncte;
/*******************************/
/// FUNCTIONS

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

    puncte.resize(N);
    for (auto &p: puncte)
        cin >> p.x >> p.y;
}
///-------------------------------------
inline int det(const Punct &a, const Punct &b, const Punct &c)
{
    double o = (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);

    if (fabs(o) <= EPS) return 0;

    if (o > 0) return 1;
    return -1;
}
///-------------------------------------
inline double dist2(const Punct &p)
{
    return pow((p.x - p0.x), 2) + pow((p.y - p0.y), 2);
}
///-------------------------------------
inline bool cmp(const Punct &a, const Punct &b)
{
    int o = det(p0, a, b);

    if (o == 0)
    {
        return dist2(a) < dist2(b);
    }

    if (o == 1) return 0;
    return 1;
}
///-------------------------------------
inline void Solution()
{
    int min_idx = 0;
    double min_y = puncte[0].y; 
    for (int i = 1 ; i < N ; ++ i)
    {
        if (puncte[i].y < min_y || (fabs(puncte[i].y - min_y) <= EPS && puncte[i].x < puncte[min_idx].x))
        {
            min_y = puncte[i].y;
            min_idx = i;
        }
    }

    swap(puncte[0], puncte[min_idx]);

    p0 = puncte[0];
    sort(puncte.begin() + 1, puncte.end(), cmp);

    vector <Punct> st;
    st.push_back(puncte[0]);
    st.push_back(puncte[1]);
    for (int i = 2 ; i < N ; ++ i)
    {
        while (st.size() >= 2 && det(st[st.size() - 1], st[st.size() - 2], puncte[i]) != 1)
            st.pop_back();
        
        st.push_back(puncte[i]);
    }

    cout << st.size() << "\n";
    for (auto p: st)
        cout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
}
///-------------------------------------
inline void Output()
{

}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}