Cod sursa(job #705012)

Utilizator aloneForever Alone alone Data 2 martie 2012 23:05:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <algorithm>

#define NMAX 120050
#define INF 0x3f3f3f3f

using namespace std;

struct punct {
	double x, y;
};

int V[NMAX], N, M, pmin;
double xmin, ymin;
punct P[NMAX];

bool cmp (punct, punct), convex (int, int, int);
void infasuratoare (), input (), output ();

int main () {
	
	input ();
	
	infasuratoare ();
	
	output ();
	
	return 0;
}

void infasuratoare () {
	
	swap (P[1], P[pmin]);
	sort (P + 2, P + 1 + N, cmp);
	
	M = 2; V[1] = 1, V[2] = 2;
	for (int i = 3; i <= N; i++) {
		while (M > 2 && !convex (V[M-1], V[M], i)) M--;
		V[++M] = i;
	}
}

bool cmp (punct a, punct b) {
	
	return a.x * b.y > b.x * a.y;
}

bool convex (int a, int b, int c) {
	
	double x1 = P[a].x, y1 = P[a].y, x2 = P[b].x, y2 = P[b].y, x3 = P[c].x, y3 = P[c].y;
	
	double r = (x3 - x2) * (y1 - y2) + (x1 - x2) * (y2 - y3);
	
	if (r > 0) return 1;
	return 0;
}

void input () {
	
	freopen ("infasuratoare.in", "r", stdin);
	
	scanf ("%d", &N); 
	
	xmin = ymin = INF;
	for (int i = 1; i <= N; i++) {
		scanf ("%lf %lf", &P[i].x, &P[i].y);
		if (P[i].y < ymin)
			xmin = P[i].x, ymin = P[i].y, pmin = i;
	}
	
	for (int i = 1; i <= N; i++)
		P[i].x -= xmin, P[i].y -= ymin;
}

void output () {
	
	freopen ("infasuratoare.out", "w", stdout);
	
	printf ("%d\n", M);
	for (int i = 1; i <= M; i++)
		printf ("%.6lf %.6lf\n", P[ V[i] ].x + xmin, P[ V[i] ].y + ymin);
}