Cod sursa(job #2451990)

Utilizator nTropicGravityesadasdwaadwqafr nTropicGravity Data 29 august 2019 01:42:48
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include    <fstream>
#include    <algorithm>
#include    <iomanip>

using namespace std;

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

#define ARRAY_MAX 120001

struct Point {
    double x, y;
};

int N, top;
Point arr[ARRAY_MAX];
Point stackData[ARRAY_MAX];

void Read() {
    fin >> N;

    for (int i = 1; i <= N; i++)
        fin >> arr[i].x >> arr[i].y;
}

double angularCoefficient(Point& A, Point& B, Point& C) {
    return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}

int compareValue(Point& firstVal, Point& secondVal) {
    return angularCoefficient(arr[1], firstVal, secondVal) < 0;
}

void sortPoints() {
    int currentPosition = 1;

    for (int i = 2; i <= N; i++)
        if (arr[i].x < arr[currentPosition].x)
            currentPosition = i;

    swap(arr[1], arr[currentPosition]);
    sort(arr + 2, arr + N + 1, compareValue);
}

void GrahamScan() {
    sortPoints();

    stackData[1] = arr[1];
    stackData[2] = arr[2];
    top = 2;

    for (int i = 3; i <= N; i++) {
        while (top >= 2 && angularCoefficient(stackData[top - 1], stackData[top], arr[i]) > 0)
            top--;

        stackData[++top] = arr[i];
    }

}

void Write() {
    fout << fixed << top << "\n";

    for (int i = top; i >= 1; i--)
        fout << setprecision(6) <<stackData[i].x << " " << stackData[i].y << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    Read();
    GrahamScan();
    Write();
}