Cod sursa(job #2142045)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 24 februarie 2018 18:15:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include <iomanip>
using namespace std;

struct point {
    double x, y, rad;
};

bool cmp(const point& a, const point& b) {
    return a.rad < b.rad;
}

bool is_convex(point a, point b, point c) {
    double det = (a.x - c.x) * (b.y - a.y) + (a.x - b.x) * (a.y - c.y);
    return det >= 0;
}

vector<point> convex_hull(vector<point>& A) {
    vector<point> H(A.size());
    H[0] = A[0];
    H[1] = A[1];
    int h_size = 2;

    for (int i = 2; i < A.size(); i++) {
        while (h_size > 1 && !is_convex(H[h_size - 2], H[h_size - 1], A[i])) {
            h_size--;
        }
        H[h_size++] = A[i];
    }

    H.resize(h_size);
    return H;
}


int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    int N;
    cin>>N;
    vector<point> A(N);

    int o_i, i;
    double o_x, o_y;
    for (i = 0; i < N; i++) {
        cin >> A[i].x >> A[i].y;
        if (i == 0 || A[i].x < o_x || (A[i].x == o_x && A[i].y < o_y)) {
            o_i = i; o_x = A[i].x; o_y = A[i].y;
        }
    }

    point aux = A[0]; 
    A[0] = A[o_i]; 
    A[o_i] = aux;

    for (i = 1; i < N; i++) {
        A[i].rad = atan2(A[i].y - A[0].y, A[i].x - A[0].x);
    }

    sort(A.begin() + 1, A.end(), cmp);
    vector<point> V = convex_hull(A);

    cout << V.size() << endl;
    cout << fixed;
    cout << setprecision(6);
    for (i = 0; i < V.size(); i++) {
        cout << V[i].x << ' ' << V[i].y << endl;
    }

    return 0;
}