Cod sursa(job #289726)

Utilizator rupraRupra C rupra Data 26 martie 2009 22:22:30
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 100100

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

struct point { 
	int x, y;
	point( int _x, int _y ) { x = _x, y = _y; }
	point() {}
};
vector<point> Up, Down;
int M, N, i, j;

point ref;
bool operator<( const point& A, const point& B ) { 
	int Adx = A.x-ref.x, Ady = A.y-ref.y;
	int Bdx = B.x-ref.x, Bdy = B.y-ref.y;
	return Adx*Bdy > Ady*Bdx; 
}

void convex( vector<point> &A ) {
	int t=0, i;
	for ( i=1; i<N; ++i ) 
		if ( A[i].y < A[t].y || (A[i].y==A[t].y && A[i].x<A[t].x) ) 
			t = i;
	ref = A[t];
	sort(A.begin(), A.end()); 

	vector<point> r;
	r.push_back(A[0]);
	r.push_back(A[1]);
	r.push_back(A[2]);
	for ( i=3; i<N; ++i ) {
		while ( r.size()>=2 ) {
			ref = r[r.size()-2];
			if ( r[r.size()-1] < A[i] ) 
				break;
			r.pop_back();
		}
		r.push_back(A[i]);
	}
	A = r;
}

inline int next( int y, int n ) { return (y==n-1) ? 0 : y+1; }
inline int prev( int y, int n ) { return (y==0) ? n-1 : y-1; }
inline int sgn( long long x ) { return x==0 ? 0 : (x<0 ? -1 : 1); }

bool test( point A, point B, point C ) { 
	// testam pe Up[next(j)] daca e deasupra dreptei det de Down[i] si Up[j]
	long long a = B.y - A.y;
	long long b = A.x - B.x;
	long long c = (long long)A.y*B.x - (long long)A.x*B.y;
	return sgn(a*b) * sgn(a*C.x + b*C.y + c) >= 0;
}

int main() {
	// load
	in >> N;
	for ( i=0; i<N; ++i ) {
		int x, y1, y2;
		in >> x >> y1 >> y2;
		Down.push_back(point(x, y1));
		Up.push_back(point(x, y2));
	}
	// magic stuff
	convex(Up); 
	convex(Down);
	N = Down.size(); M = Up.size();
	j = 1;
	for ( i=N-1; i>=0; --i ) {
		int bk = j;
		do {
			if ( test(Down[i], Down[j], Down[next(j, M)]) )
				break;
			else
				j = next(j, M);
		} while ( j!=bk );
		if ( test(Down[i], Down[next(i, N)], Up[j]) && test(Down[i], Down[prev(i, N)], Up[j]) ) {
			out << Down[i].x << " " << Down[i].y << " ";
			out << Up[j].x << " " << Up[i].y;
			out << "\n";
			return 0;
		}
	}
	return 0;
}