Cod sursa(job #588824)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 9 mai 2011 18:39:15
Problema Oypara Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<stdio.h>
#include<algorithm>

#define maxN 100005
#define INF (1 << 29)

using namespace std;

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

int n,i,x,y1,y2,nrs,nrj;

struct pct{
	int x;
	int y;
}A[maxN],B[maxN],aux,S[maxN],J[maxN],Stv[maxN],pct1,pct2;


inline int max(int a,int b){
	return a > b ? a : b;
}

inline int min(int a,int b){
	return a < b ? a : b;
}

bool det( pct a , pct b , pct c ){
	
	long long d = 1LL * (a.x-c.x)*(b.y-c.y) + 1LL * ( a.y - c.y ) * ( c.x - b.x );
	
	if ( d < 0 ) 
		return 1;
	
	return 0;
	
}

struct cmp{
	inline bool operator ( ) ( const pct &a, const pct &b ){
		double ctg1; double ctg2;
		
		ctg1 = (double)a.x / a.y; ctg2 = (double)b.x / b.y;
		
		if ( ctg1 != ctg2 ) return ctg1 > ctg2;
		
		return a.x < b.x;
		
	}
};

inline void citire () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		
		fscanf(f,"%d %d %d",&x,&y1,&y2);
		
		aux.x = x; aux.y = min(y1,y2); B[i] = aux;
		aux.y = max(y1,y2); A[i] = aux;
		
	}
	
}

int infasuratoare ( pct V[maxN] , pct A[maxN] ){
	
	int vf = 0,ymin = INF,pozmin,xmin;
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( V[i].y < ymin ) ymin = V[i].y,xmin = V[i].x,pozmin = i;
		Stv[i].x = Stv[i].y = 0;
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		V[i].x -= xmin; V[i].y -= ymin;
	}
	
	aux = V[1]; V[1] = V[pozmin] ; V[pozmin] = aux;
	
	sort( V+2 , V+n+1, cmp( ) );
	
	for ( i = 1 ; i <= n ; ++i ){
		
		while ( vf > 1 && det(Stv[vf-1],Stv[vf],V[i]) ){
			--vf;
		}
		
		Stv[++vf] = V[i];
		
	}
	
	for ( i = 1 ; i <= vf ; ++i ){
		aux.x = Stv[i].x + xmin; aux.y = Stv[i].y + ymin;
		A[i] = aux;
	}
	
	return vf;
	
}

inline int urmatorul(int j){
	++j;
	if ( j > nrs )
		j = 1;
	return j;
}

inline int anteriorul(int j ){
	--j;
	if ( !j )
		j = nrs;
	return j;
}

inline bool conditie (int i,int j) {
	
	if ( !det(J[i],S[j],S[urmatorul(j)]) && !det(J[i],S[j],S[anteriorul(j)]) ){
		return 1;
	}
	
	return 0;
	
}

inline int urmatorul2(int i){
	++i;
	if ( i > nrj )
		i = 1;
	return i;
}

inline int anteriorul2(int i){
	--i;
	if ( !i ){
		i = nrj;
	}
	return i;
}

inline bool solutie ( int i , int j ){
	
	if ( !det(S[j],J[i],J[urmatorul2(i)]) && !det(S[j],J[i],J[anteriorul2(i)]) ){
		return 1;
	}
	
	return 0;
	
}

inline void find () {
	
	int i , j , k , xmin = INF , gasit = 0;
	
	for ( k = 1 ; k <= nrj ; ++k ){
		if ( J[k].x < xmin )
			xmin = J[k].x,i = k;
	}
	
	xmin = INF;
	
	for ( k = 1 ; k <= nrs ; ++k ){
		if ( S[k].x < xmin )
			xmin = S[k].x , j = k;
	}
	
	for ( ; !gasit ; i = anteriorul2(i) ){
		
		while ( !conditie(i,j) ){
			j = urmatorul(j);
		}
		
		if ( solutie(i,j) ){
			gasit = 1;
			pct1 = J[i]; pct2 = S[j];
		}
		
	}
	
	fprintf(g,"%d %d %d %d\n",pct1.x,pct1.y,pct2.x,pct2.y);
	
}


int main () {
	
	citire();
	
	nrs = infasuratoare( A , S ); nrj = infasuratoare ( B , J );
	
	find();
	
	fclose(f);
	fclose(g);
	
	return 0;
}