Cod sursa(job #1341270)

Utilizator stefantrettTrett Stefan stefantrett Data 12 februarie 2015 16:32:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

#define Nmax 120005
#define x first
#define y second

using namespace std;

pair <double, double> pct[Nmax], S[Nmax];
int N, vf;

double det(pair<double, double> A, pair<double, double> B, pair<double, double> C)
    {
        return ((B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y));
    }

class cmp{
public:
    bool operator() (const pair<double, double> &A, const pair<double, double> &B) const
    {
        return (det(pct[1], A, B) < 0);
    }
};

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

    scanf("%d", &N);

    for(int i=1;i<=N;++i)
        scanf("%lf%lf", &pct[i].x, &pct[i].y);

    int ind = 1;

    for(int i=2;i<=N;++i)
        if(pct[i] < pct[ind])
            ind = i;

    swap(pct[1], pct[ind]);
    sort(pct+2, pct+N+1, cmp());

    vf++;
    S[vf] = pct[1];
    vf++;
    S[vf] = pct[2];

    for(int i=3;i<=N;++i)
    {
        while(vf>=2 && det(S[vf-1], S[vf], pct[1]) > 0)
            --vf;
        vf++;
        S[vf] = pct[i];
    }

    printf("%d\n", vf);

    while(vf)
    {
        printf("%lf %lf\n", S[vf].x, S[vf].y);
        vf--;
    }

    return 0;
}