Cod sursa(job #2402054)

Utilizator CiprianC11Constantinescu Ciprian CiprianC11 Data 10 aprilie 2019 12:15:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

double e = 1e-12;

struct po { double x, y; };

inline double cp(po a, po b, po c) { return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x); };

inline int ccw(po a, po b, po c)
{
    double x = cp(a, b, c);
    if(fabs(x) < e) return 0;
    if(x > e) return 1;
    return -1;
}

vector<po> v;
vector<int> st;

bool cmp(po a, po b) { return ccw(v[0], a, b) == 1; }

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n;
    double x, y;
    scanf("%d", &n);
    scanf("%lf%lf", &x, &y), v.push_back({x, y});
    for(int i = 1; i < n; i++)
    {
        scanf("%lf%lf", &x, &y), v.push_back({x, y});
        if(y < v[0].y or (y == v[0].y and x < v[0].x)) v.pop_back(), v.push_back(v[0]), v[0] = {x, y};
    }
    sort(v.begin() + 1, v.end(), cmp);
    v.push_back(v[0]);
    st.push_back(0), st.push_back(1);
    for(int i = 2; i <= n;)
    {
        if(ccw(v[st[st.size() - 2]], v[st[st.size() - 1]], v[i]) > 0) st.push_back(i), i++;
        else st.pop_back();
    }
    printf("%d\n", st.size() - 1);
    for(int i = 0; i < st.size() - 1; i++) printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
    return 0;
}