Cod sursa(job #1722025)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 iunie 2016 01:28:08
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int N_MAX = 100005;

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  bool operator <(const Point &o) const { return 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, Top, nUpper, nLower;
Point Stack[N_MAX];
Point Upper[N_MAX];
Point Lower[N_MAX];

int main() {
  ifstream f("oypara.in");
  ofstream g("oypara.out");
  
  int x, yLower, yUpper;
  
  f >> N;
  for(int i = 1; i <= N; i++) {
    f >> x >> yLower >> yUpper;
    Upper[++nUpper] = Point(x, yUpper);
    Lower[++nLower] = Point(x, yLower);
  }
  
  sort(Upper + 1, Upper + nUpper + 1);  
  Stack[1] = Upper[1];
  Stack[2] = Upper[2];
  Top = 2;
  for(int i = 3; i <= nUpper; i++) {
    while(Top > 1 && Det(Stack[Top - 1], Stack[Top], Upper[i]) <= 0)
      Top--;
    Stack[++Top] = Upper[i];
  }
  nUpper = Top;
  for(int i = 1; i <= nUpper; i++)
    Upper[i] = Stack[i];
  
  sort(Lower + 1, Lower + nLower + 1);
  Stack[1] = Lower[1];
  Stack[2] = Lower[2];
  Top = 2;
  for(int i = 3; i <= nLower; i++) {
    while(Top > 1 && Det(Stack[Top - 1], Stack[Top], Lower[i]) >= 0)
      Top--;
    Stack[++Top] = Lower[i];
  }
  nLower = Top;
  for(int i = 1; i <= nLower; i++)
    Lower[i] = Stack[i];
  
  int i, j;
  for(i = 1, j = 1; i < nLower; i++) {
    while(Det(Lower[i], Upper[j], Upper[j + 1]) <= 0)
      j++;
    if(Det(Lower[i], Lower[i + 1], Upper[j]) >= 0) {
      g << Lower[i].x << " " << Lower[i].y << " " << Upper[j].x << " " << Upper[j].y << "\n";
      return 0;
    }
  }
  
  return 0;
}