Cod sursa(job #861880)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 21 ianuarie 2013 23:05:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>

using namespace std;

#define MAXN 120050
int N;
struct Point {
    double x, y;
};

Point P[MAXN];
bool used[MAXN];
Point st[MAXN];
int head;

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

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

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

    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%lf %lf", &P[i].x, &P[i].y);
    }

    int first = 0;
    for(int i = 0; i < N; i++)
        if(P[i].y < P[first].y)
            first = i;

    swap(P[0], P[first]);

    sort(P + 1, P + N, cmp);

    st[0] = P[0];
    st[1] = P[1];

    head = 1;
    for(int i = 2; i < N; i++) {
        while(head >= 1 && crossProduct(st[head - 1], st[head], P[i]) < 0)
            head--;
        st[++head] = P[i];
    }

    printf("%d\n", head + 1);
    for(int i = 0; i <= head; i++)
        printf("%.6lf %.6lf\n", st[i].x, st[i].y);

	return 0;
}