Cod sursa(job #695743)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 februarie 2012 14:19:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <algorithm>

//#define double long double

const double eps = 0.0000001;
const int maxn = 120005;

using namespace std;

inline double fabs(double x) {
	if(x < eps) return -x;
	return x;
}

struct Punct {
		double x, y;
} v[maxn];
		
int ord[maxn], st[maxn], N; 
bool uz[maxn];

inline bool cmp(const Punct &a, const Punct &b) {
	if(fabs(a.x - b.x) < eps) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

inline bool semn(int i, int j, int k) {
	double x1 = v[i].x, x2 = v[j].x, x3 = v[k].x, y1 = v[i].y, y2 = v[j].y, y3 = v[k].y;
	
	return ( x1 * y2 + x2 * y3 + y1 * x3 - y2 * x3 - y3 * x1 - y1 * x2) < eps;
}

void ConvexHull() {
	int i = 3, step = 1, k = 0;
	uz[2] = 1; st[++k] = 1; st[++k] = 2;
	
	while(!uz[1]) {
		
		while(uz[i]) {
			if(i == N)
				step = -1;
			i += step;
		}
		
		for(; semn(st[k - 1], st[k], i) && k >= 2;  ) {
			uz[st[k]] = 0; k--;
		}
		
		st[++k] = i; uz[i] = 1;
		
	//	i += step; printf("%d\n", step);
	}
	printf("%d\n", k - 1);
	for(int i = 1; i < k; i++)
		printf("%lf %lf\n", v[st[i]].x, v[st[i]].y); 
}	

int main() {
	
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d\n", &N);
	
	for( int i = 1; i <= N; ++i ) {
		scanf("%lf%lf\n", &v[i].x, &v[i].y);
		//printf("%Lf %Lf\n", v[i].x, v[i].y);
	
	}	
	sort( v + 1, v + N + 1, cmp); 
	//for( int i = 1; i <= N; ++i ) printf("%lf %lf\n", v[i].x, v[i].y);
	ConvexHull();
	return 0;
}