Cod sursa(job #3195708)

Utilizator Robilika2007Robert Badea Robilika2007 Data 21 ianuarie 2024 15:37:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");

#define CW -1
#define COL 0
#define CCW 1
#define MAX_N 120000

struct pct
{
    double x, y;
}v[MAX_N];
int n;
vector <pct> st;

double orientation(const pct& a, const pct& b, const pct& c) {
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

bool cmp(const pct& a, const pct& b)
{
    return orientation(v[0], a, b) < 0;
}

void infasurareConvexa()
{
    st.push_back(v[0]);
    st.push_back(v[1]);

    for(int i = 2; i < n; ++i)
    {
        while(st.size() >= 2 && orientation(st[st.size() - 2], st.back(), v[i]) >= 0)
        {
            st.pop_back();
        }
        st.push_back(v[i]);
    }
}

int main()
{
    double x, y;
    in >> n;
    for(int i = 0; i < n; ++i)
    {
        in >> x >> y;
        v[i] = {x, y};
        if(y > v[0].y)
        {
            swap(v[0], v[i]);
        } else if(y == v[0].y && x > v[0].x)
        {
            swap(v[0], v[i]);
        }
    }

    sort(v + 1, v + n, cmp);

    infasurareConvexa();

    out << st.size() << '\n';

    out << setprecision(12) << fixed;
    for(int i = 0; i < st.size(); ++i)
    {
        out << st[i].x << " " << st[i].y << '\n';
    }

    return 0;
}