Pagini recente » Cod sursa (job #1789717) | Cod sursa (job #333613) | Cod sursa (job #999656) | Cod sursa (job #2415961) | Cod sursa (job #289726)
Cod sursa(job #289726)
#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;
}