Cod sursa(job #3159211)

Utilizator AlexDavid26Alex Bleotu AlexDavid26 Data 20 octombrie 2023 22:11:22
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Point {
    double x, y;
};

enum Orientation {
    COLINEAR,
    CLOCKWISE,
    COUNTER_CLOCKWISE
};

Orientation calculateOrientation(Point p1, Point p2, Point p3) {
    double det = (p2.x - p1.x) * (p3.y - p1.y) -
                 (p3.x - p1.x) * (p2.y - p1.y);

    if (det > 0) return CLOCKWISE;
    else if (det < 0) return COUNTER_CLOCKWISE;
    else return COLINEAR;
}

Point points[120005], poligon[120005];
int length, poligonLength;

void buildPoligonTop() {
    for (int i = 0; i < length; i++) {
        while (poligonLength >= 2 &&
               calculateOrientation(poligon[poligonLength - 2],
                                    poligon[poligonLength - 1],
                                    points[i]) != CLOCKWISE)
            poligonLength--;

        poligon[poligonLength++] = points[i];
    }
}

void buildPoligonBottom() {
    for (int i = length - 3; i >= 0; i--) {
        while (poligonLength >= 2 &&
               calculateOrientation(poligon[poligonLength - 2],
                                    poligon[poligonLength - 1],
                                    points[i]) != CLOCKWISE)
            poligonLength--;

        poligon[poligonLength++] = points[i];
    }
}

int main() {
    fout << fixed << setprecision(6);

    fin >> length;
    for (int i = 0; i < length; i++)
        fin >> points[i].x >> points[i].y;

    sort(points, points + length, [](Point p1, Point p2) {
        return p1.x == p2.x ? p1.y > p2.y : p1.x < p2.x;
    });

    buildPoligonTop();
    buildPoligonBottom();

    poligonLength--;

    fout << poligonLength << "\n";
    for (int i = 0; i < poligonLength; i++)
        fout << poligon[i].x << " " << poligon[i].y << "\n";
}