Cod sursa(job #2817207)

Utilizator ElizaTElla Rose ElizaT Data 13 decembrie 2021 11:09:48
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 12e4;
int st[NMAX + 5];
struct Pct {
    double x,y;
    bool operator<(Pct a) {
        if (a.x == x)
            return a.y < y;
        return a.x < x;
    }
}v[NMAX + 5],aux;

double dif(Pct a, Pct b, Pct c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(Pct a, Pct b) {
    return dif(v[0], a, b) < 0;
}
int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n,poz,cnt;
    fin >> n >> v[0].x >> v[0].y;
    poz = 0;
    for (int i = 1;i < n;i++) {
        fin >> v[i].x >> v[i].y;
        if (v[i] < v[poz])
            poz = i;
    }
    aux = v[0];
    v[0] = v[poz];
    v[poz] = aux;
    sort(v + 1, v + n, cmp);
    st[0] = 0;
    st[1] = 1;
    cnt = 2;
    for (int i = 2;i < n;i++) {
        while (cnt >= 2 && dif(v[st[cnt - 2]], v[st[cnt - 1]], v[i]) > 0)
            cnt--;
        st[cnt++] = i;
    }
    fout << cnt << '\n';
    fout << fixed;
    for (int i = cnt - 1;i >= 0;i--)
        fout << setprecision(8) << v[st[i]].x << " " << v[st[i]].y << '\n';
    return 0;
}