Cod sursa(job #661780)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 15 ianuarie 2012 11:12:59
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <math.h>

long i, n, mm, mM, poz, k, ptc, dex[120010], j, pt[120010];
double x[120010], y[120010], A, B, C, max = 0;

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%lf %lf", &x[i], &y[i]);
		if (max < y[i]) max = y[i], poz = i;
	}
	
	dex[poz] = 1;
	pt[++ptc] = poz;
	//prima dreapta
	for (j = 1; j <= n; ++j) {
		if (x[j] < x[poz] && !dex[j]) {
			A = y[j] - y[poz];
			B = x[poz] - x[j];
			C = x[j] * y[poz] - x[poz] * y[j];
			long mm = 0, mM = 0;
			for (k = 1; k <= n; ++k) {
				if (k != poz && k != j) {
					if (A * x[k] + B * y[k] + C > 0) ++mM;
					if (A * x[k] + B * y[k] + C < 0) ++mm;
				}
			}
			if (mm == 0 || mM == 0) {
				pt[++ptc] = j;
				dex[j] = 1;
				break;
			}
		}
	}
	
	for (i = 2; i <= ptc; ++i) {
		for (j = 1; j <= n; ++j) {
			if (!dex[j]) {
				A = y[j] - y[pt[i]];
				B = x[pt[i]] - x[j];
				C = x[j] * y[pt[i]] - x[pt[i]] * y[j];
				long mm = 0, mM = 0;
				for (k = 1; k <= n; ++k) {
					if (k != pt[i] && k != j) {
						if (A * x[k] + B * y[k] + C > 0) ++mM;
						if (A * x[k] + B * y[k] + C < 0) ++mm;
					}
				}
				if (mm == 0 || mM == 0) {
					pt[++ptc] = j;
					dex[j] = 1;
					break;
				}
			}
		}
	}
	
	printf("%ld\n", ptc);
	for (i = 1; i <= ptc; ++i) printf("%.6lf %.6lf\n", x[pt[i]], y[pt[i]]);
	
	return 0;
}