Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok

Cod sursa(job #388001)

Utilizator bixcabc abc bixc Data 28 ianuarie 2010 23:39:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 120010

struct punct {double x, y, ctg;} v[Nmax], aux;
void citire (), afisare ();

double xmin, ymin;
int pmin, n, N;
int S[Nmax];

int pozitie (long double x1, long double y1, long double x2, long double y2, long double x3, long double y3){
	long double A;
	A = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1);
	if (A >= 0) return 0;
	return 1;
} 

int cmp (const punct &a, const punct &b) {
	return a.ctg > b.ctg;
}

void infasuratoare () {
	
	aux = v[1]; v[1] = v[pmin]; v[pmin] = aux;
	v[1].x = v[1].y = 0;
	int i;
	for (i = 2; i <= n; i++) {
		v[i].x-= xmin;
		v[i].y-= ymin;
		
		v[i].ctg = v[i].x / v[i].y;		
	}
	
	sort (v + 2, v + 1 + n, cmp);
	
	v[n+1] = v[1];
	S[++N] = 1;
	for (i = 2; i <= n + 1; i++) {
		while (N >= 2 && pozitie (v[S[N]].x, v[S[N]].y, v[S[N-1]].x, v[S[N-1]].y, v[i].x, v[i].y)) 
			N--;
		
		S[++N] = i;
	}
}

int main () {
	
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	
	citire ();
	infasuratoare ();
	afisare ();

	return 0;
}

void citire () {
	
	scanf ("%d", &n);
	scanf ("%lf %lf", &v[1].x, &v[1].y);
	xmin = v[1].x; ymin = v[1].y;
	
	for (int i = 2; i <= n; i++) {
		scanf ("%lf %lf", &v[i].x, &v[i].y);
		if (ymin > v[i].y || ( ymin == v[i].y && xmin > v[i].x )) {
			xmin = v[i].x;
			ymin = v[i].y;
			pmin = i;
		}
	}	
}

void afisare () {

	printf ("%d\n", N - 1);
	for (int i = 1; i < N; i++)
		printf ("%lf %lf\n", v[S[i]].x + xmin, v[S[i]].y + ymin);
}