Cod sursa(job #426058)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 26 martie 2010 13:19:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
struct stiva{
	double x;
	double y;
} v[120001],s[120001];
int i,n,p;
int w[100];
struct punct{
	double x;
	double y;
} punct_initial;
int compar(stiva a,stiva b){
	if( b.x * a.y > a.x*b.y )
		   return 1;
	if( a.x * b.y == b.x * a.y && a.x<b.x)
		return 1;
return 0;	
}

void translatie(){
	for(i=1;i<=n;i++){
		v[i].x-=punct_initial.x;
		v[i].y-=punct_initial.y;
	}
}
int fct(int a,int b,int c){
	return ((s[b].x-v[a].x)*(s[c].y-v[a].y)-(s[b].y-v[a].y)*(s[c].x-v[a].x)>0);	
}
int main(){
	fscanf(f,"%d",&n);
punct_initial.x=2000000001;
for(i=1;i<=n;i++){
	fscanf(f,"%lf%lf",&v[i].x,&v[i].y);	
    if(v[i].x< punct_initial.x){
           punct_initial.x=v[i].x;
           punct_initial.y=v[i].y;
}		   
   else if(v[i].x==punct_initial.x && punct_initial.y >v[i].y)
         punct_initial.y=v[i].y;
}

translatie();
sort(v+1,v+n+1,compar);
s[1]=v[1];
s[2]=v[2];
p=2;
for(i=3;i<=n;i++) //parcurgem punctele
{ while(!fct(i,p,p-1)&&p>1)
          	p--;
  p++;
  s[p]=v[i];	
}
for(i=p;i>=1;i--)
	fprintf(g,"%.12lf %.12lf\n",s[i].x+punct_initial.x,s[i].y+punct_initial.y);
return 0;
}