Cod sursa(job #300602)

Utilizator katakunaCazacu Alexandru katakuna Data 7 aprilie 2009 15:50:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
using namespace std;
#include <cstdio>
#include <algorithm>

#define Nmax 120010

struct punct { long double x, y, tg;} v[Nmax], aux;
int n, i, poz, p, S[Nmax];
long double xmin, ymin;

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

int cmp(punct a, punct b){
	return a.tg < b.tg;
}

int main(){

	FILE *f = fopen("infasuratoare.in", "r");
	FILE *g = fopen("infasuratoare.out", "w");

	fscanf(f,"%d",&n);
	fscanf(f,"%Lf %Lf",&v[1].x, &v[1].y);
	poz = 1; xmin = v[1].x; ymin = v[1].y;
	
	for(i = 2; i <= n; i++){
		fscanf(f,"%Lf %Lf",&v[i].x, &v[i].y);
		if( v[i].x < xmin || ( v[i].x == xmin && v[i].y < ymin ) )
			poz = i, xmin = v[i].x, ymin = v[i].y;
	}
	
	aux = v[1]; v[1] = v[poz]; v[poz] = aux;
	v[1].x = v[1].y = 0;
	v[n + 1] = v[1];
	S[++p] = 1;
	
	for(i = 2; i <= n; i++){
		v[i].x-= xmin; v[i].y-= ymin;
		v[i].tg = v[i].y / v[i].x;
	}
	
	sort(v + 2, v + 1 + n, cmp);
	
	for(i = 2; i <= n + 1; i++){
		S[++p] = i;
		while( p > 2 && arie( v[S[p-1]].x, v[S[p-1]].y, v[S[p]].x, v[S[p]].y, v[S[p-2]].x, v[S[p-2]].y) )
			S[--p] = S[p + 1], S[p + 1] = 0;
	}
	
	fprintf(g,"%d\n",p - 1);
	for(i = 2; i <= p ; i++)
		fprintf(g,"%Lf %Lf\n",v[S[i]].x + xmin, v[S[i]].y + ymin);
	
	fclose(f);
	fclose(g);
	
	return 0;
	
}