Cod sursa(job #1165842)

Utilizator poptibiPop Tiberiu poptibi Data 2 aprilie 2014 23:17:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 120010;

int N, K, HS;
pair<double, double> P[NMAX], Stack[NMAX], Hull[NMAX];

double Det(pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
    return A.first * (B.second - C.second) + B.first * (C.second - A.second) + C.first * (A.second - B.second);
}

void Add()
{
    K = 0;
    Stack[K ++] = P[1];
    Stack[K ++] = P[2];
    for(int i = 3; i <= N; ++ i)
    {
        while(K >= 2 && Det(Stack[K - 2], Stack[K - 1], P[i]) < 0) K --;
        Stack[K ++] = P[i];
    }
    for(int i = 0; i < K - 1; ++ i)
        Hull[++ HS] = Stack[i];
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i) scanf("%lf %lf", &P[i].first, &P[i].second);

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

    printf("%i\n", HS);
    for(int i = 1; i <= HS; ++ i)
        printf("%.6lf %.6lf\n", Hull[i].first, Hull[i].second);
}