Cod sursa(job #714980)

Utilizator DSzprogDombi Szabolcs DSzprog Data 16 martie 2012 13:44:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <algorithm>
#include <cstdio>
#include <cmath>

struct Vect {
	float x, y;
	void operator += (Vect v) {
		x += v.x;
		y += v.y;
	}
	void operator -= (Vect v) {
		x -= v.x;
		y -= v.y;
	}
};

int points;
Vect point[120002];
#define px(i) point[i].x
#define py(i) point[i].y

void swap(int a, int b) {
	Vect swap = point[a];
	point[a] = point[b];
	point[b] = swap;
}

bool cmp(Vect a, Vect b) {
	return(atan2(a.y, a.x) < atan2(b.y, b.x));
}

bool ccw(int a, int b, int c) {
	return((px(b) - px(a)) * (py(c) - py(a)) < (py(b) - py(a)) * (px(c) - px(a)));
}

int main() {
	FILE * in = fopen("infasuratoare.in", "rt");
	FILE * out = fopen("infasuratoare.out", "wt");

	fscanf(in, "%d", &points);
	int my = 1;
	for (int i = 1; i <= points; ++i) {
		fscanf(in, "%f%f", &point[i].x, &point[i].y);
		if (py(i) < py(my)) {
			my = i;
		}
	}
	swap(1, my);
	for (int i = 2; i <= points; ++i) {
		point[i] -= point[1];
	}
	std::sort(point + 2, point + points + 1, cmp);
	for (int i = 2; i <= points; ++i) {
		point[i] += point[1];
	}

	int k = 1;
	point[0] = point[points];
	for (int i = 2; i <= points; ++i) {
		while (ccw(k - 1, k, i)) {
			--k;
		}
		++k;
		swap(i, k);
	}

	fprintf(out, "%d\n", k);
	for (int i = 1; i <= k; ++i) {
		fprintf(out, "%f %f\n", point[i].x, point[i].y);
	}

	fclose(in);
	fclose(out);
}