Pagini recente » Cod sursa (job #1889435) | Cod sursa (job #2048217) | Cod sursa (job #1984533) | Cod sursa (job #1696293) | Cod sursa (job #1539849)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
struct Point {
int x, y;
Point() {
x = 0;
y = 0;
}
Point(int x, int y) {
this->x = x;
this->y = y;
}
bool operator < (const Point a) const {
return (x == a.x ? y > a.y : x > a.x);
}
};
vector<Point> up, down, hullUp, hullDown;
bool convex(const Point &a, const Point &b, const Point &c) {
return 1LL * (a.x - c.x)*(b.y - c.y) - 1LL * (a.y - c.y)*(b.x - c.x) <= 0LL;
}
vector<Point> getConvexHull(vector<Point> points, bool rev) {
sort(points.begin(), points.end());
if (rev)
reverse(points.begin(), points.end());
vector<Point> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for (unsigned int i = 2; i < points.size(); ++i) {
while (hull.size() > 1 && !convex(hull[hull.size() - 2], hull[hull.size() - 1], points[i]))
hull.pop_back();
hull.push_back(points[i]);
}
return hull;
}
int main() {
ifstream fin("oypara.in");
ofstream fout("oypara.out");
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
int x, yUp, yDown;
fin >> x >> yDown >> yUp;
up.push_back(Point(x, yUp));
down.push_back(Point(x, yDown));
}
hullUp = getConvexHull(up, false);
hullDown = getConvexHull(down, true);
Point solUp;
for (unsigned int i = 0, j = 0; i + 1 < hullUp.size(); ++i) {
while (j < hullDown.size() && !convex(hullUp[i], hullUp[i + 1], hullDown[j]))
++j;
if (j == hullDown.size()) {
solUp = hullUp[i];
break;
}
}
Point solDown;
for (unsigned int i = 0; i + 1 < hullDown.size(); ++i) {
if (!convex(hullDown[i], hullDown[i + 1], solUp)) {
solDown = hullDown[i];
break;
}
}
fout << solUp.x << ' ' << solUp.y << ' ' << solDown.x << ' ' << solDown.y << '\n';
return 0;
}
//Trust me, I'm the Doctor!