Cod sursa(job #2740898)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 14 aprilie 2021 18:13:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-12;
const int Nmax = 2e5;

struct pct {
    double x, y;
    int pos;
};

pct v[2 * Nmax + 5];
char vaz[Nmax + 5];
vector<int> hull;

double det(pct p, pct q, pct r) {
    return q.x * r.y + p.x * q.y + p.y * r.x - p.y * q.x - q.y * r.x - p.x * r.y;
}

// 0 -> coliniare, 1 -> viraj stanga, 2 -> viraj dreapta
int viraj(pct p, pct q, pct r) {
    double d = det(p, q, r);
    if (abs(d) < eps) return 0;
    if (d > 0) return 1;
    return 2;
}

bool cmp(pct a, pct b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;
    pct q;
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> v[i].x >> v[i].y;
        v[i].pos = i;
    }
    for (int i = 1; i < n; ++i) v[n + i] = v[n - i];
    sort(v + 1, v + n + 1, cmp);
    hull.push_back(1);
    for (int i = 2; i < 2 * n; ++i) {
        if (vaz[v[i].pos]) continue;
        while (hull.size() > 1 && viraj(v[hull[hull.size() - 2]], v[hull.back()], v[i]) == 2) {
            vaz[v[hull.back()].pos] = 0;
            hull.pop_back();
        }
        hull.push_back(i);
        vaz[v[i].pos] = 1;
    }
    hull.pop_back();
    out << hull.size() << "\n";
    out << setprecision(10) << fixed;
    for (p : hull) out << v[p].x << " " << v[p].y << "\n";
    return 0;
}