Cod sursa(job #897120)

Utilizator deividFlorentin Dumitru deivid Data 27 februarie 2013 18:56:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<algorithm>

#define maxn 120005
#define inf (1LL<<62)

using namespace std;

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

int n;
int st[maxn];

struct pct{
	double x,y;
	double ctg;
}A[maxn];

struct cmp{
	inline bool operator () ( const pct &a , const pct &b ){
		return a.ctg > b.ctg;
	}
};

double det ( const pct &a , const pct &b , const pct &c ){
	
	double d = (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);
	return d;
}

void infasuratoare ( int &n , pct *S ){
	
	double xmin = inf,ymin = inf; int poz = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		if ( S[i].y < ymin || (S[i].y == ymin && S[i].x < xmin ) ){
			ymin = S[i].y;
			xmin = S[i].x;
			poz = i;
		}
	}
	
	swap(S[1],S[poz]); S[1].x = S[1].y = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		S[i].x -= xmin; S[i].y -= ymin;
		S[i].ctg = S[i].x/S[i].y;
	}
	
	sort(S+2,S+n+1,cmp());
	
	for ( int i = 1 ; i <= n ; ++i ){
		
		while ( st[0] > 1 && det(S[i],S[st[st[0]]],S[st[st[0]-1]]) > 0 ){
			st[st[0]--] = 0;
		}
		st[++st[0]] = i;
	}
	
	for ( int i = 1 ; i <= st[0] ; ++i ){
		S[i] = S[st[i]];
		S[i].x += xmin; S[i].y += ymin;
	}
	for ( int i = st[0]+1 ; i <= n ; ++i )	S[i].x = S[i].y = S[i].ctg = 0;
	n = st[0];
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	}
	
	infasuratoare(n,A);
	
	fprintf(g,"%d\n",n);
	for ( int i = 1 ; i <= n ; ++i ){
		fprintf(g,"%lf %lf\n",A[i].x,A[i].y);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}