Cod sursa(job #1164420)

Utilizator cbanu96Banu Cristian cbanu96 Data 2 aprilie 2014 03:11:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define FILEIN "infasuratoare.in"
#define FILEOUT "infasuratoare.out"
#define NMAX 120005
#define EPS 1e-12

struct Pct {
    double x;
    double y;

    bool operator<(const Pct& other) const {
        if (this->x == other.x)
            return this->y < other.y;

        return this->x < other.x;
    };
};

Pct P[NMAX];
int N;

vector<int> sol;

double CrossProduct(Pct &O, Pct &A, Pct &B) {
    return (O.x - A.x) * (O.y - B.y) - (O.y - A.y) * (O.x - B.x);
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d", &N);

    for ( int i = 1; i <= N; i++ ) {
        double x, y;
        scanf("%lf %lf", &x, &y);

        P[i].x = x, P[i].y = y;
    }

    sort(P+1, P+N+1);

    sol.resize(N); int solCnt = 0;

    for ( int i = 1; i <= N; i++ ) {
        while (solCnt >= 2 && CrossProduct(P[sol[solCnt - 2]], P[sol[solCnt - 1]], P[i]) <= EPS)
            solCnt--;
        sol[solCnt++] = i;
    }

    int upper = solCnt + 1;

    for ( int i = N; i >= 1; i-- ) {
        while (solCnt >= upper && CrossProduct(P[sol[solCnt - 2]], P[sol[solCnt - 1]], P[i]) <= EPS)
            solCnt--;
        sol[solCnt++] = i;
    }

    printf("%d\n", solCnt - 1);
    for ( int i = 1; i < solCnt; i++ ) {
        printf("%.6lf %.6lf\n", P[sol[i]].x, P[sol[i]].y);
    }

    return 0;
}