Pagini recente » Cod sursa (job #3121590) | Cod sursa (job #281839) | Cod sursa (job #1387313) | Cod sursa (job #990161) | Cod sursa (job #1801416)
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
bool operator < (const Point &other) const {
return x < other.x;
}
};
inline long long det(Point A, Point B, Point C) {
return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}
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(stiv[st - 1], stiv[st], v[i]) >= 0LL)
--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(up[i], up[i + 1], down[j]) >= 0LL)
++j;
--i;
for (j = 0; det(down[j], down[j + 1], up[i]) < 0LL; ++j) {}
ofstream fout("oypara.out");
fout << up[i].x << " " << up[i].y << " " << down[j].x << " " << down[j].y << '\n';
fout.close();
return 0;
}