Cod sursa(job #1708715)

Utilizator UPB_Darius_Rares_SilviuPeace my pants UPB_Darius_Rares_Silviu Data 27 mai 2016 20:43:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 120005

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point {
    double x, y;
}a[NMAX], st[NMAX];

int N, indexMin = 1, top;

double crossedProduct(point A, point B, point C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

void convexHull() {
    top = 2;
    st[1] = a[1];
    st[2] = a[2];

    for (int i = 3; i <= N; ++i) {
        while (top > 1 && crossedProduct(st[top - 1], st[top], a[i]) > 0) {
            --top;
        }

        st[++top] = a[i];
    }
}

int cmp(const point &A, const point &B) {
    return crossedProduct(a[1], A, B) < 0;
}

int main() {
    f >> N;
    for (int i = 1; i <= N; ++i) {
        f >> a[i].x >> a[i].y;
        if (a[i].x < a[indexMin].x) {
            indexMin = i;
        } else if (a[i].x == a[indexMin].x && a[i].y < a[indexMin].y) {
            indexMin = i;
        }
    }

    swap(a[1], a[indexMin]);
    sort(a + 2, a + N + 1, cmp);
    convexHull();
    g << top << '\n';
    g << fixed << setprecision(7);
    for (int i = top; i; --i) {
        g << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}