Cod sursa(job #1404557)

Utilizator razboi4Manole Iulian razboi4 Data 28 martie 2015 12:45:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<bits/stdc++.h>

#define Nmax 120001
#define X first
#define Y second
#define Punct pair < double , double >

using namespace std;

Punct Point[Nmax], Stiva[Nmax];
int N, H;

double product(Punct A, Punct B, Punct C)
{
    return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}

bool cmp(Punct A, Punct B)
{
    return product(Point[1], A, B) < 0;
}

void Read()
{
    freopen("infasuratoare.in", "r", stdin);
    scanf("%d", &N);
    for(int i = 1; i <= N; ++ i) {
        scanf("%lf %lf", &Point[i].X, &Point[i].Y);
        if(Point[i] < Point[1])
            swap(Point[i], Point[1]);
    }
}

void Write()
{
    freopen("infasuratoare.out", "w", stdout);
    printf("%d", H);
    for(int i = H; i; -- i)
        printf("\n%lf %lf", Stiva[i]);
}

void Infasuratoare()
{
    sort(Point + 2, Point + 1 + N, cmp);

    Stiva[1] = Point[1];
    Stiva[(H = 2)] = Point[2];

    for(int i = 3; i <= N; Stiva[++ H] = Point[i], ++ i)
        while(H >= 2 && product(Stiva[H - 1], Stiva[H], Point[i]) > 0)
            -- H;
    Write();
}

int main()
{
    Read();
    Infasuratoare();
    return 0;
}