Cod sursa(job #2714207)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 1 martie 2021 15:04:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<double, double> Point;

inline double cross_product(Point O, Point A, Point B) {
    return (A.first - O.first) * (B.second - O.second)
        - (B.first - O.first) * (A.second - O.second);
}

int main() {
    FILE * f;
    int n;

    f = fopen("infasuratoare.in", "r");
    fscanf(f, "%d", &n);
    vector<Point> points(n);
    int min_pos = 0;
    for (int i = 0; i < n; ++i) {
        fscanf(f, "%lf%lf", &points[i].first, &points[i].second);
        if (points[i] < points[min_pos]) {
            min_pos = i;
        }
    }
    fclose(f);

    /*
     * sort the points in clockwise order by the polar angle
     * made with the point that has the lowest coordinates
     */
    swap(points[0], points[min_pos]);
    sort(
        points.begin() + 1,
        points.end(),
        [&](Point A, Point B) {return cross_product(points[0], A, B) < 0;}
    );

    vector<Point> convex_hull(n);
    convex_hull[0] = points[0];
    convex_hull[1] = points[1];
    int hull_size = 1;
    for (int i = 2; i < n; ++i) {
        while (
            hull_size >= 1 &&
            cross_product(convex_hull[hull_size - 1], convex_hull[hull_size], points[i]) >= 0
        ) {
            --hull_size;
        }
        ++hull_size;
        convex_hull[hull_size] = points[i];
    }

    f = fopen("infasuratoare.out", "w");
    fprintf(f, "%d\n", hull_size + 1);
    while (hull_size >= 0) {
        fprintf(f, "%.6lf %.6lf\n", convex_hull[hull_size].first, convex_hull[hull_size].second);
        --hull_size;
    }
    fclose(f);

    return 0;
}