Cod sursa(job #778662)

Utilizator savimSerban Andrei Stan savim Data 15 august 2012 13:14:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 120010
#define inf 2147000000 

int n, i, j, h;
struct punct {
	double x;
	double y;
} V[MAX_N], Stiv[MAX_N];

void cit() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);	

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%lf %lf", &V[i].x, &V[i].y); 
}

long double tangenta(punct A, punct B) {
	if (A.x != B.x)	return (long double) (A.y - B.y) / (A.x - B.x);
	else return inf;
}

inline int cmp(punct A, punct B) {
	return (long double) tangenta(A, V[1]) < tangenta(B, V[1]);
}

long double semn(punct A, punct B, punct C) {
	return (long double) A.x * B.y + B.x * C.y + C.x * A.y - 
			 		     A.x * C.y - B.x * A.y - C.x * B.y;
}

void solve() {
	//gasesc cel mai din stanga punct, si la egalitate cel mai de jos
	V[n + 1].x = V[n + 1].y = inf;
	j = n + 1;

	for (i = 1; i <= n; i++)
    	if (V[i].x < V[j].x) j = i;
		else if (V[i].x == V[j].x && V[i].y < V[j].y)
				j = i;

	//sortez punctele dupa tangenta cu acest punct
	swap(V[1], V[j]);
	
	sort(V + 2, V + n + 1, cmp);

	//bag elementele in stiva
	h = 1;
	Stiv[1] = V[1];

	for (i = 2; i <= n; i++) {
        Stiv[++h] = V[i];
			
		while (h >= 3 && semn(Stiv[h - 2], Stiv[h - 1], Stiv[h]) < 0) {
			Stiv[h - 1] = Stiv[h];
			h--;
		}
	}
}

void write() {
	printf("%d\n", h);
	for (i = 2; i <= h; i++)
		printf("%lf %lf\n", Stiv[i].x, Stiv[i].y);
	printf("%lf %lf\n", Stiv[1].x, Stiv[1].y);
}

int main() {

	cit();
	solve();
	write();

	return 0;
}