Cod sursa(job #1801323)

Utilizator cella.florescuCella Florescu cella.florescu Data 8 noiembrie 2016 21:21:12
Problema Oypara Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x, y;
  bool operator < (const Point &other) const {
    if (x == other.x)
      return y < other.y;
    return x < other.x;
  }
};

inline int det_is_neg(Point A, Point B, Point C) {
  return (1LL* (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) <= 0LL);
}

const int MAXN = 1e5 + 1;

Point up[MAXN], down[MAXN], stiv[MAXN];
Point *v;

int get_convex_hull(int n, int ord) {
  int i, st = -1;
  sort(v, v + n);
  if (ord)
    reverse(v, v + n);
  for (i = 0; i < n; ++i) {
    while (st > 0 && det_is_neg(stiv[st - 1], stiv[st], v[i]))
      --st;
    stiv[++st] = v[i];
  }
  for (i = 0; i <= st; ++i)
    v[i] = stiv[i];
  return st + 1;
}

int main()
{
    int n, i, x, y1, y2, u, d, j;
    ifstream fin("oypara.in");
    fin >> n;
    for (i = 0; i < n; ++i) {
      fin >> x >> y1 >> y2;
      up[i] = {x, y2};
      down[i] = {x, y1};
    }
    fin.close();
    v = up; u = get_convex_hull(n, 0);
    v = down; d = get_convex_hull(n, 1);
    for (i = j = 0; j < d; ++i)
      while (j < d && det_is_neg(up[i], up[i + 1], down[j]))
        ++j;
    --i;
    for (j = 0; det_is_neg(down[j], down[j + 1], up[i]) == 0; ++j) {}
    ofstream fout("oypara.out");
    fout << up[i].x << " " << up[i].y << " " << down[j].x << " " << down[j].y << '\n';
    fout.close();
    return 0;
}