Cod sursa(job #942950)

Utilizator razvan.popaPopa Razvan razvan.popa Data 23 aprilie 2013 21:54:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define Point pair<double, double>
#define x first
#define y second
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define nMax 120005
using namespace std;

Point P[nMax], S[nMax];

double ARIA;

int N, NS;

void read(){
    freopen(infile, "r", stdin);

    scanf("%d", &N);

    FOR(i,1,N){
        scanf("%lf %lf", &P[i].x, &P[i].y);

        if(P[i] < P[1])
            swap(P[1], P[i]);
    }

    fclose(stdin);
}

double crossProduct(const Point &O, const Point &A, const Point &B){
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

bool cmp(const Point &A, const Point &B){
    return crossProduct(P[1], A, B) > 0;
}

void solve(){
    sort(P + 2, P + N + 1, cmp);

    FOR(i,1,N){
        while(NS > 1 && crossProduct(S[NS - 1], S[NS], P[i]) < 0)
            NS --;
        S[++ NS] = P[i];
    }

    /*FOR(i,3,NS)
        ARIA += crossProduct(S[1], S[i-1], S[i]);
    ARIA /= 2.0;*/
}

void print(){
    freopen(outfile, "w", stdout);

    printf("%d\n", NS);
    FOR(i,1,NS)
        printf("%.6lf %.6lf\n", S[i].x, S[i].y);

    fclose(stdout);
}

int main(){
    read();
    solve();
    print();

    return 0;
}