Cod sursa(job #3353512)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 7 mai 2026 19:33:02
Problema Oypara Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#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';
  }

  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;
}