Cod sursa(job #1503196)

Utilizator visanrVisan Radu visanr Data 15 octombrie 2015 18:19:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 120010;

int N, Top, HSZ;
pair<double, double> P[NMAX], Stack[NMAX], Hull[NMAX];

double Det(pair<double, double> P1, pair<double, double> P2, pair<double, double> P3)
{
    return P1.first * (P2.second - P3.second) + P2.first * (P3.second - P1.second) + P3.first * (P1.second - P2.second);
}

void AddPoints()
{
    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) Hull[++ HSZ] = 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);
    AddPoints();
    reverse(P + 1, P + N + 1);
    AddPoints();

    printf("%i\n", HSZ);
    for(int i = 1; i <= HSZ; ++ i) printf("%.10f %.10f\n", Hull[i].first, Hull[i].second);
}