Cod sursa(job #3280427)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 26 februarie 2025 14:26:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
double x, y;
struct punct
{
    long double x, y;
    friend bool operator<(const punct &a, const punct &b)
    {
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
};
vector<punct> pct;
vector<punct> st;
double cwp(punct p, punct a, punct b)
{
    return (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y);
}
bool cmp(punct a, punct b)
{
    return cwp(pct[1], a, b) < 0;
}
void convex()
{
    st.push_back(pct[1]);
    st.push_back(pct[2]);
    int head = 2;
    for(int i=3; i<=n; i++)
    {
        while(st.size() >= 2 && cwp(st[st.size()-2], st[st.size()-1], pct[i]) > 0)
            st.pop_back();
        st.push_back(pct[i]);
    }
}
int main()
{
    cin >> n;
    pct.resize(n+1);
    for(int i=1; i<=n; i++)
        cin >> pct[i].x >> pct[i].y;
    sort(pct.begin() + 1, pct.end());
    sort(pct.begin() + 2, pct.end(), cmp);
    convex();
    cout << st.size() << '\n';
    reverse(st.begin(), st.end());
    for(auto i:st)
        cout << fixed << setprecision(6) << i.x << " " << i.y << '\n';
    return 0;
}