Cod sursa(job #1121707)

Utilizator visanrVisan Radu visanr Data 25 februarie 2014 13:46:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 120010;

int N, Top, K;
pair<double, double> P[NMAX], Stack[NMAX], ConvexHull[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 Solve()
{
    Top = 0;
    Stack[Top ++] = P[1]; Stack[Top ++] = P[2];
    for(int i = 3; i <= N; ++ i)
    {
        while(Top >= 2 && Det(Stack[Top - 2], Stack[Top - 1], P[i]) < 0) Top --;
        Stack[Top ++] = P[i];
    }

    for(int i = 0; i < Top - 1; ++ i) ConvexHull[++ K] = 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);
    Solve();

    reverse(P + 1, P + N + 1);
    Solve();

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