Cod sursa(job #2207932)

Utilizator EclipseTepes Alexandru Eclipse Data 27 mai 2018 14:04:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define dMAX 120000

using namespace std;

int n, pos = 1, h;

typedef pair<double, double> Point;

Point arr[dMAX + 2], myStack[dMAX + 2];

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

double CrossProduct(Point e1, Point e2, Point e3) {
    return (e2.x - e1.x) * (e3.y - e1.y) - (e2.y - e1.y) * (e3.x - e1.x);
}

bool Compare(Point e1, Point e2) {
    return CrossProduct(arr[1], e1, e2) < 0;
}

int main() {
    int i, j;
    fin >> n;
    fin >> arr[1].x >> arr[1].y;
    for (i = 2; i <= n; i++) {
        fin >> arr[i].x >> arr[i].y;
        if (arr[i] < arr[pos]) pos = i;
    }
    swap(arr[1], arr[pos]);
    sort(arr + 2, arr + n + 1, Compare);
    myStack[++h] = arr[1];
    myStack[++h] = arr[2];
    for (i = 3; i <= n; i++) {
        while (h >= 2 && CrossProduct(myStack[h - 1], myStack[h], arr[i]) > 0)
            h--;
        myStack[++h] = arr[i];
    }
    fout << h << '\n';
    for (i = h; i >= 1; i--) {
        fout << setprecision(9) << fixed << myStack[i].x << ' ' << myStack[i].y << '\n';
    }
}