Cod sursa(job #2404046)

Utilizator gabib97Gabriel Boroghina gabib97 Data 12 aprilie 2019 11:32:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

#define N 120005
using namespace std;

int n;
struct point {
    double x, y;
} P[N];

int st[N], last;

double determinant(const point &p0, const point &p1, const point &p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

double dist(const point &a, const point &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

void convexHull() {
    st[1] = 0;
    st[2] = 1;
    last = 2;

    for (int i = 2; i < n; i++) {
        double d = determinant(P[st[last - 1]], P[st[last]], P[i]);

        if (d < 0) {
            while (d < 0) {
                last--;
                d = determinant(P[st[last - 1]], P[st[last]], P[i]);
            }
            st[++last] = i;
        } else if (d == 0)
            st[last] = i;
        else
            st[++last] = i;
    }
}

int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    cin >> n;
    double xmin = DBL_MAX, ymin = DBL_MAX;
    int extremum = 0;
    for (int i = 0; i < n; i++) {
        cin >> P[i].x >> P[i].y;

        if (P[i].y < ymin || (P[i].y == ymin && P[i].x < xmin)) {
            xmin = P[i].x;
            ymin = P[i].y;
            extremum = i;
        }
    }

    swap(P[extremum], P[0]);
    sort(P + 1, P + n, [](const point &a, const point &b) {
        double det = determinant(P[0], a, b);
        return det > 0 || (det == 0 && dist(P[0], a) < dist(P[0], b));
    });
    convexHull();

    cout << last << '\n';
    for (int i = 1; i <= last; i++)
        cout << fixed << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << '\n';
    return 0;
}