Cod sursa(job #1722300)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 iunie 2016 20:27:38
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.52 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int N_MAX = 100005;

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  inline bool operator <(const Point &o) const { return (x == o.x ? y < o.y : x < o.x); } 
};

int64_t Det(const Point &A, const Point &B, const Point &C) {
  return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (C.x - A.x) * (B.y - A.y);
}

int N, nUpper, nLower;
Point Upper[N_MAX];
Point Lower[N_MAX];

void getConvex(Point P[], int &Size, bool Order) {
  Point Stack[N_MAX];
  int Top;
  
  sort(P+1, P+Size+1);
  if(Order == 1) reverse(P+1, P+Size+1);
  Stack[1] = P[1];
  Stack[2] = P[2];
  Top = 2;
  for(int i = 3; i <= Size; i++) {
    while(Top > 1 && Det(Stack[Top - 1], Stack[Top], P[i]) >= 0LL) Top--;
    Stack[++Top] = P[i];
  } 
  Size = Top;
  for(int i = 1; i <= Size; i++)
    P[i] = Stack[i];
} 

int main() {
  ifstream f("oypara.in");
  ofstream g("oypara.out");
    
  f >> N;
  for(int i = 1, x, yD, yU; i <= N; i++) {
    f >> x >> yD >> yU;
    Upper[++nUpper] = Point(x, yU);
    Lower[++nLower] = Point(x, yD);
  }
  
  getConvex(Upper, nUpper, 1);
  getConvex(Lower, nLower, 0);

  int U = 1, D = 1;
  while(D < nLower) {
    while(U < nUpper && Det(Lower[D], Upper[U], Upper[U + 1]) < 0LL)
      U++;
    if(Det(Lower[D], Lower[D + 1], Upper[U]) >= 0) {
      g << Lower[D].x << " " << Lower[D].y << " " << Upper[U].x << " " << Upper[U].y << "\n";
      break;
    }
    D++;
  }
    
  return 0;
}