Cod sursa(job #387613)

Utilizator bixcabc abc bixc Data 28 ianuarie 2010 00:07:40
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 120010

struct punct {double x, y, ctg;} v[Nmax], aux;
int n, i, pmin;
int S[Nmax];
double xmin, ymin;
void citire (), afisare ();

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

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

void infasuratoare () {
	
	aux = v[pmin]; v[pmin] = v[1]; v[1] = aux;
	v[1].x = v[1].y = 0;
	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 + n + 1, cmp);
	
	v[n + 1] = v[1];
	S[++S[0]] = 1;
	for (i = 2; i <= n + 1; i++) {
		while (S[0] > 2 && pozitie ( v[ S[S[0]] ].x, v[ S[S[0]] ].y, v[ S[S[0] - 1] ].x, v[ S[S[0] - 1] ].y, v[i].x, v[i].y)) 
			S[0]--;
		
		S[++S[0]] = 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 (i = 2; i <= n; i++) {
		scanf ("%lf %lf", &v[i].x, &v[i].y);
		if (v[i].y < ymin || (v[i].y == ymin && v[i].x  < xmin)) {
			xmin = v[i].x;
			ymin = v[i].y;
			pmin = i;
		}
	}
}

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