Cod sursa(job #863504)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 23 ianuarie 2013 21:12:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 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];
int st[MAXN];
int head;
bool v[MAXN];

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 A.y < B.y || (A.y == B.y && A.x < B.x);
    if(A.x < B.x)
        return true;
    if(A.x > B.x)
        return false;
    return A.y < B.y;
}

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);
    }

    sort(P, P + N, cmp);

    st[0] = 0;
    st[1] = 1;
    v[1] = true;

    head = 1;
    int dir = 1;
    for(int i = 2; i >= 0; i += dir) {
        if(i == N) {
            dir = -dir;
            continue;
        }
        if(v[i]) continue;

        while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[i]) < 0) {
            v[st[head]] = false;
            head--;
        }
        v[i] = true;
        st[++head] = i;
    }

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


	return 0;
}