Cod sursa(job #872181)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 5 februarie 2013 21:07:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<algorithm>
#include<string.h>
#define DIM 120010

using namespace std;


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

int n;
double X_min , Y_min;

struct punct{
	double x ;
	double y;
}V[DIM],aux;

void swap(int x){
	aux=V[x];
	V[x]=V[n];
	V[n]=aux;
}
void read(){
	f>>n;
	
	int i , p_min=1;
	
	for(i=1;i<=n;i++){
		f>>V[i].x>>V[i].y;
		if(V[i].y<V[p_min].y)
			p_min=i;
		else if(V[i].y==V[p_min].y)
			if(V[i].x<V[p_min].x)
				p_min=i;
	}
	swap(p_min);
	X_min=V[n].x;Y_min=V[n].y;
	n--;
}

int cmp(punct a , punct b){
	double p1=a.y*b.x;
	double p2=b.y*a.x;
	
	if(p1>p2)
		return 0;
	
	return 1;
	
}

long double semn(punct a, punct b , punct c){
	return ((long double)b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

void infasuratoare(){
	
	int S[DIM];
	
	int vf=2 , i;
	
	memset(S,0,sizeof(S));S[vf]=1;
	
	for(i=2;i<=n;i++){
		
		while(semn(V[S[vf-1]],V[S[vf]],V[i])<=0&&vf>=1){
			vf--;
		}
		
		S[++vf]=i;
		
	}
	
	fprintf(g,"%d\n",vf);
	
	for(i=1;i<=vf;i++)
		fprintf(g,"%.6f %.6f \n",V[S[i]].x+X_min,V[S[i]].y+Y_min);
	
}


int main(){
	
	read();
	
	for(int i=1;i<=n;i++){
		V[i].x-=X_min;
		V[i].y-=Y_min;
	}
	
	sort(V+1,V+n+1,cmp);
	
	infasuratoare();
	
	return 0;
}