Cod sursa(job #1414745)

Utilizator BaTDucKMocanu George BaTDucK Data 2 aprilie 2015 22:47:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<bits/stdc++.h>

#define Nmax 120005
#define Point pair < double , double >
#define X first
#define Y second

using namespace std;

int N, Sol_DIM;
Point Punct[Nmax], Sol[Nmax];

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

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

void _Read()
{
    int ind = 1;

    freopen("infasuratoare.in","r", stdin);

    scanf("%d", &N);
    for(int i = 1; i <= N; ++ i) {
        scanf("%lf %lf", &Punct[i].X, &Punct[i].Y);
        if(Punct[i] < Punct[ind])
            ind = i;
    }

    swap(Punct[ind], Punct[1]);
    sort(Punct + 2, Punct + 1 + N, _cmp);
}

void _Write()
{
    freopen("infasuratoare.out", "w", stdout);

    printf("%d\n", Sol_DIM);
    for(int i = 1; i <= Sol_DIM; ++ i)
        printf("%lf %lf\n", Sol[i]);
}

void _Infasuratoare()
{
    Sol[1] = Punct[1];
    Sol[Sol_DIM = 2] = Punct[2];

    for(int i = 3; i <= N; ++ i) {
        while(Sol_DIM >= 2 && _produs(Sol[Sol_DIM - 1], Sol[Sol_DIM], Punct[i]) > 0)
            Sol_DIM --;
        Sol[++ Sol_DIM] = Punct[i];
    }

    _Write();
}

int main()
{
    _Read();
    _Infasuratoare();

    return 0;
}