Pagini recente » Cod sursa (job #267436) | Cod sursa (job #922372) | Cod sursa (job #2948976) | Cod sursa (job #1704869) | Cod sursa (job #1601192)
#include <bits/stdc++.h>
using namespace std;
typedef int64_t i64;
const int NMAX = 100010;
int N;
struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
bool operator <(const Point &rhs) const {
return (x == rhs.x) ? (y < rhs.y) : (x < rhs.x);
}
bool operator >(const Point &rhs) const {
return (x == rhs.x) ? (y > rhs.y) : (x > rhs.x);
}
};
vector<Point> Up, Down;
i64 Area(Point A, Point B, Point C) {
return i64(B.x - A.x) * (C.y - A.y) - i64(C.x - A.x) * (B.y - A.y);
}
void LowerEnvelope(vector<Point> &hull) {
sort(hull.begin(), hull.end());
vector<Point> curr;
curr.push_back(hull[0]);
curr.push_back(hull[1]);
for (int i = 2; i < int(hull.size()); ++i) {
while (curr.size() > 1 && Area(curr[curr.size() - 2], curr[curr.size() - 1], hull[i]) <= 0)
curr.pop_back();
curr.push_back(hull[i]);
}
curr.push_back(hull[0]);
swap(hull, curr);
}
void UpperEnvelope(vector<Point> &hull) {
sort(hull.begin(), hull.end(), greater<Point>());
vector<Point> curr;
curr.push_back(hull[0]);
curr.push_back(hull[1]);
for (int i = 2; i < int(hull.size()); ++i) {
while (curr.size() > 1 && Area(curr[curr.size() - 2], curr[curr.size() - 1], hull[i]) <= 0)
curr.push_back(hull[i]);
}
curr.push_back(hull[0]);
swap(hull, curr);
}
int main() {
ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
assert(freopen("oypara.in", "r", stdin) != NULL);
assert(freopen("oypara.out", "w", stdout) != NULL);
assert(freopen("debug.err", "w", stderr) != NULL);
#endif
int i, j, x, y1, y2;
cin >> N;
for (i = 1; i <= N; ++i) {
cin >> x >> y1 >> y2;
Up.push_back(Point(x, y2));
Down.push_back(Point(x, y1));
}
LowerEnvelope(Up);
UpperEnvelope(Down);
int solup = -1, soldown = -1;
for (i = 0, j = 0; i + 1 < int(Up.size()); ++i) {
while (j < int(Down.size()) && Area(Up[i], Up[i + 1], Down[j]) <= 0)
++j;
if (j == Down.size()) {
solup = i;
break;
}
}
for (i = 0; i + 1 < int(Down.size()); ++i) {
if (Area(Down[i], Down[i + 1], Up[solup]) <= 0) {
soldown = i;
break;
}
}
cout << Up[solup].x << ' ' << Up[solup].y << ' ' << Down[soldown].x << ' ' << Down[soldown].y << '\n';
return 0;
}