Pagini recente » Cod sursa (job #2075935) | Cod sursa (job #1236518) | Cod sursa (job #2611263) | Cod sursa (job #2862489) | Cod sursa (job #1805079)
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int SPQR = 100005;
struct PTX {
int x, y;
bool operator < (const PTX &arg) const {
return (x == arg.x) ? (y < arg.y) : (x < arg.x); } };
int n, p0, p1;
vector<PTX> pts[2], hull[2];
inline i64 ccw(const PTX &a, const PTX &b, const PTX &c) {
return (1LL * a.x - b.x) * (c.y - b.y) - (1LL * a.y - b.y) * (c.x - b.x); }
void make_hulls(void) {
sort(pts[0].begin(), pts[0].end());
sort(pts[1].rbegin(), pts[1].rend());
for(int h = 0; h < 2; ++h)
for(int i = 0; i < n; ++i) {
while(hull[h].size() > 1 && ccw(hull[h][hull[h].size() - 2], hull[h][hull[h].size() - 1], pts[h][i]) > 0)
hull[h].pop_back();
hull[h].push_back(pts[0][i]); } }
void get_calipers(void) {
int i, j;
for(i = 0, j = 0; i < hull[0].size() - 1 && j < hull[1].size(); ++i)
for(; j + 1 < hull[1].size() && ccw(hull[0][i], hull[0][i + 1], hull[1][j]) <= 0; ++j);
-- i;
p0 = i;
p1 = j; }
int main(void) {
freopen("oypara.in", "r", stdin);
freopen("oypara.out", "w", stdout);
scanf("%d", &n);
pts[0].resize(n);
pts[1].resize(n);
for(int i = 0; i < n; ++i) {
scanf("%d%d%d", &pts[0][i].x, &pts[0][i].y, &pts[1][i].y);
pts[1][i].x = pts[0][i].x; }
make_hulls();
get_calipers();
printf("%d %d %d %d\n", pts[0][p0].x, pts[0][p0].y , pts[1][p1].x, pts[1][p1].y);
return 0; }