Pagini recente » Statistici Capata Ioana (aalleexxaa) | Cod sursa (job #3253543) | Cod sursa (job #2907749) | Cod sursa (job #2235295) | Cod sursa (job #1143170)
#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);
}