Cod sursa(job #925897)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 24 martie 2013 20:10:14
Problema Oypara Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<fstream>
#include<algorithm>
#include<string.h>

using namespace std;

#define max_n 100010
#define inf 2000000000

ifstream f("oypara.in");
ofstream g("oypara.out");

struct punct{
	int x , y;
}P1[max_n] , P2[max_n];

int n , x , y1 , y2 , k1 , k2 , semn1 , semn2 , s1 , p1 , p2;
int Fig1[max_n] , Fig2[max_n];

void read(){
	
	f>>n;
	
	for(int i = 1; i<= n ; i++){
		f>>x>>y1>>y2;
		if(y1>y2) swap(y1 , y2);
		P1[i].x = x; P1[i].y = y1;
		P2[i].x = x; P2[i].y = y2;
	}
	
}

int cmp(punct a , punct b){
	return a.y * b.x < a.x * b.y;
}

void reduce(punct P[] ,int &x_min ,int &y_min){
	int minim = inf , p_min;
	for(int i = 1 ; i <= n ; i++){
		if( P[i].y < minim ){
			minim = P[i].y ; p_min = i;
		}
		else if(P[i].y == minim && P[i].x < P[p_min].x)
			p_min = i;
	}
	
	x_min = P[p_min].x ; y_min = P[p_min].y;
	
	swap(P[p_min] , P[n]);
	
	for(int i = 1 ; i <= n ; i++){
		P[i].x -= x_min; P[i].y -= y_min;
	}
}

int det(punct a , punct b , punct c){
	int semn = ( b.x - a.x ) * ( c.y - a.y ) - ( c.x - a.x ) * ( b.y - a.y );
	if(semn<0) return 0;
	return 1;
}

void infasuratoare(punct P[] , int Fig[] , int &k){
	
	int x_min , y_min , u;
	
	reduce(P , x_min , y_min);
	sort(P+1 , P+n , cmp);
	
	Fig[1] = n; Fig[2] = 1 ; u = 2;
	
	for(int i = 2 ; i < n ; i++){
		
		while( u >= 2 && det( P[Fig[u]] , P[Fig[u-1]] , P[i] ) )
			u--;
		
		Fig[++u] = i;
		
	}
	k = u;
	
	for(int i = 1 ; i<=n ; i++){
		P[i].x += x_min; P[i].y += y_min;
	}
	
}

void solve(){
	
	int i;
	
	Fig1[0] = Fig1[k1] ; memcpy(Fig1+k1+1 , Fig1 + 1 , sizeof(int)*k1);
	Fig2[0] = Fig2[k2] ; memcpy(Fig2+k2+1 , Fig2 + 1 , sizeof(int)*k2);
	
	p1 = 1;
	for(i=2;i<=k1;i++){
		if(P1[Fig1[i]].x<P1[Fig1[p1]].x)
			p1 = i;
	}
	
	p1+=k1;
	
	p2 = 1;
	for(i=2;i<=k2;i++){
		if(P2[Fig2[i]].x>P1[Fig2[p2]].x)
			p2 = i;
	}
	
	while(true){
		
		do{
			semn1 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P2[Fig2[p2+1]]);
			semn2 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P2[Fig2[p2-1]]);
		}while(semn1!=semn2 && ( p2++ ));
		
		s1 = semn1;
		
		semn1 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P1[Fig1[p1+1]]);
		semn2 = det(P1[Fig1[p1]] , P2[Fig2[p2]] , P1[Fig1[p1-1]]);
		
		if(semn1==semn2){
			if(s1!=semn1){
				g<<P1[Fig1[p1]].x<<" "<<P1[Fig1[p1]].y<<" "<<P2[Fig2[p2]].x<<" "<<P2[Fig2[p2]].y<<"\n";
				break;
			}
		}
		p1--;
	}
	
}

int main(){
	
	read();
	
	infasuratoare(P1 , Fig1 , k1);
	infasuratoare(P2 , Fig2 , k2);
	
	solve();
	
	return 0;
}