Cod sursa(job #402560)

Utilizator n3msizN3msiz n3msiz Data 23 februarie 2010 22:40:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<algorithm>
#define nmax 120005

using namespace std;

int n,i,pmin,k;
double minx,miny;
int a[nmax];

struct punct{
	double x,y;
};

punct v[nmax],aux;

double cmpctg(punct a, punct b){
	//return a.ctg < b.ctg;	
	
	return a.x * b.y > b.x * a.y;
}

int deter(int a, int b, int c){
	long double x1 = v[a].x;
	long double x2 = v[b].x;
	long double x3 = v[c].x;
	long double y1 = v[a].y;
	long double y2 = v[b].y;
	long double y3 = v[c].y;
	long double sol;
	sol = (x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2);
	
	if(sol>0)
		return 1;
	else
		return 0;
}

void reducere(double minxx, double minyy){
	int i;
	aux = v[1];
	v[1] = v[pmin];
	v[pmin] = aux;
	
	for(int i=2;i<=n;i++){
		v[i].x -= minxx;
		v[i].y -= minyy;
	}
	
	sort(v+2,v+1+n,cmpctg);
	
	k=2;
	a[1]=1;
	a[2]=2;
	for (i = 3; i <= n; i++) {
		while (k > 2 && !deter(a[k-1],a[k],i))
			k--;
		
		a[++k] = i;
	}

	 
}





int main(){
	FILE*f=fopen("infasuratoare.in","r");
	FILE*g=fopen("infasuratoare.out","w");
	
	fscanf(f,"%d",&n);
	miny = 1LL<<60;
	for(i=1;i<=n;i++){
		fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
		if(v[i].y<miny){
			miny=v[i].y;
			minx=v[i].x;
			pmin = i;
		}
		else
			if(v[i].y==miny){
				minx=v[i].x;
				pmin = i;
			}
		
	}
	
	reducere(minx,miny);
	
	
	fprintf(g,"%d\n%lf %lf\n",k,v[1].x,v[1].y);
	
	for (i=2;i<=k;i++)
		fprintf(g,"%lf %lf\n",v[a[i]].x+minx,v[a[i]].y+miny);

	
	fclose(f);
	fclose(g);
	
	return 0;
}