Cod sursa(job #1143170)

Utilizator toranagahVlad Badelita toranagah Data 14 martie 2014 21:16:20
Problema Oypara Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cassert>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream fin("oypara.in");
ofstream fout("oypara.out");

typedef pair<int, int> Point;
#define x first
#define y second
#define mp make_pair

const int MAX_N = 100100;
const int INF = 1 << 30;
const int UPPER = 1;
const int LOWER = -1;
const Point NOP = mp(INF, INF);

int N;
vector<Point> dn, up;
pair<Point, Point> answer;

void readfin();
void solve();
void printfout();
vector<Point> find_envelope(vector<Point> &p, int side);
pair<Point, Point> find_line(const vector<Point> &p1, const vector<Point> &p2, int side);
inline int64_t xp(const Point &O, const Point &A, const Point &B);

int main() {
	readfin();
	solve();
	printfout();
	return 0;
}

void readfin() {
	fin >> N;

  dn.resize(N); up.resize(N);
	for (int i = 0, x, y1, y2; i < N; i += 1) {
		fin >> x >> y1 >> y2;
		dn[i] = mp(x, y1);
    up[i] = mp(x, y2);
  }
}

void solve() {
  vector<Point> lower = find_envelope(dn, UPPER);
  vector<Point> upper = find_envelope(up, LOWER);

  answer = find_line(lower, upper, LOWER);
  if (answer == mp(NOP, NOP))
    answer = find_line(upper, lower, UPPER);
}

void printfout() {
  fout << answer.x.x << ' ' << answer.x.y << ' ';
  fout << answer.y.x << ' ' << answer.y.y;
}

vector<Point> find_envelope(vector<Point> &p, int side) {
  sort(p.begin(), p.end());
  vector<Point> st = {p[0], p[1]};
  for (int i = 2; i < N; i += 1) {
    while (st.size() >= 2 && xp(st[st.size() - 2], st.back(), p[i]) * side > 0) {
      st.pop_back();
    }
    st.push_back(p[i]);
  }
  return st;
}

pair<Point, Point> find_line(const vector<Point> &p1, const vector<Point> &p2, int side) {
  int n = p1.size() - 1, m = p2.size();
  for (int i = 0, j = 0; i < n; i += 1) {
    int steps = 0;
    while (steps <= m && xp(p1[i], p1[i + 1], p2[j]) * side < 0) {
      j = (j + 1) % m;
      steps += 1;
    }
    if (steps >= m and p1[i] != p1[i + 1])
      return mp(p1[i], p1[i + 1]);
  }
  return (mp(NOP, NOP));
}

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