Pagini recente » Cod sursa (job #2828019) | Cod sursa (job #332839) | Cod sursa (job #3148237) | Cod sursa (job #3223573) | Cod sursa (job #3353513)
#include <fstream>
#include <cassert>
#include <algorithm>
#include <vector>
template<class T> using vec = std::vector<T>;
using ll = long long;
struct Point {
int x, y;
Point( int x, int y ): x(x), y(y) {}
};
int sgn( ll x ) { return (x > 0) - (x < 0); }
ll det( const Point& A, const Point& B, const Point& C ) {
return -1 * ((A.x - B.x) * ll(A.y - C.y) - (A.y - B.y) * ll(A.x - C.x));
}
vec<Point> hull( vec<Point> points ) {
std::sort( points.begin(), points.end(), []( const Point& A, const Point& B ) -> bool {
if( A.x != B.x ) return A.x < B.x;
return A.y < B.y;
} );
vec<Point> ret;
for( Point P : points ){
while( (int)ret.size() >= 2 && sgn( det( ret.end()[-2], ret.end()[-1], P ) ) != +1 )
ret.pop_back();
ret.push_back( P );
}
return ret;
};
int main() {
std::ifstream fin("oypara.in");
std::ofstream fout("oypara.out");
int n;
fin >> n;
vec<Point> lower, upper; {
for( int i = 0; i < n; i++ ){
int x, y1, y2;
fin >> x >> y1 >> y2;
lower.emplace_back( x, y1 );
upper.emplace_back( x, -y2 );
}
lower = hull(lower);
upper = hull(upper);
for( auto &[x, y]: upper ) y = -y;
}
if( (int)lower.size() == 1 ) {
Point A = lower[0];
fout << A.x << ' ' << A.y << ' ' << A.x + 1 << ' ' << A.y << '\n';
return 0;
}
int idx_up = 0;
for( int i = 0; i + 1 < (int)lower.size(); i++ ){
Point A = lower[i], B = lower[i + 1];
while( idx_up - 1 >= 0 && det( A, B, upper[idx_up - 1] ) >= det( A, B, upper[idx_up] ) )
idx_up--;
while( idx_up + 1 < (int)upper.size() && det( A, B, upper[idx_up + 1] ) >= det( A, B, upper[idx_up] ) )
idx_up++;
if( det( A, B, upper[idx_up] ) > 0 ) continue;
fout << A.x << ' ' << A.y << ' ';
fout << B.x << ' ' << B.y << '\n';
return 0;
}
while(true);
return 0;
}