Cod sursa(job #709600)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 8 martie 2012 12:09:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<stdio.h>
#include<algorithm>
#define INF 1000000010

using namespace std;

FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");

int n, i, poz, k, stv[130000];
double minx, miny;


struct coord{
	double x, y;
};
coord v[130000],aux;

int scoate(double x1, double y1, double x2, double y2, double x3, double y3){
	
long double  x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);

	if(x >= 0){
		return 1;
	}
	
	
return 0;	
}

int cmp(coord a, coord b){
	return (a.x * b.y) > (a.y * b.x);
}

int main(){
	
	fscanf(fin,"%d",&n);
	
	minx = INF;
	miny = INF;
	
	v[0].x = INF;
	v[0].y = INF;
	poz = 0;
	
	for(i = 1 ; i <= n; i++){
		fscanf(fin,"%lf %lf", &v[i].x, &v[i].y);
		
		if(v[i].x < v[poz].x){
			poz = i;
		}
		else
		if(v[i].x == v[poz].x ){
			if( v[i].y < v[poz].y ){
				poz = i;
			}
		}
	}
	
	aux = v[poz];
	v[poz]=v[1];
	v[1]=aux;
	minx = v[1].x;
	miny = v[1].y;
	for(i=1 ; i <= n ; i++ ){
		v[i].x -= minx;
		v[i].y -= miny;
	}
	
	sort(v+2, v+n+1, cmp);
	
	stv[1]=1;
	stv[2]=2; k = 2;
	
	for(i=3;i<=n;i++){
		while( k>=2 && scoate( v[i].x, v[i].y,  v[stv[k]].x, v[stv[k]].y, v[stv[k-1]].x, v[stv[k-1]].y) ){
			k--;
		}
		stv[++k] = i;
	}
	
	fprintf(fout,"%d\n",k);
	
	for(i=1; i<= k; i++){
		fprintf(fout,"%lf %lf\n", v[stv[i]].x + minx , v[stv[i]].y + miny );
	}
	
	fclose(fout);
	fclose(fin);
	return 0;
}