Pagini recente » Cod sursa (job #812366) | Cod sursa (job #27155) | Cod sursa (job #1636100) | Cod sursa (job #1263631) | Cod sursa (job #1805583)
#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 i64(b.x - a.x) * (c.y - a.y) - i64(c.x - a.x) * (b.y - a.y); }
void make_hulls(void) {
sort(pts[0].begin(), pts[0].end());
sort(pts[1].begin(), pts[1].end());
for(int i = 0; i < pts[0].size(); ++i) {
while(hull[0].size() > 1 && ccw(hull[0][hull[0].size() - 2], hull[0][hull[0].size() - 1], pts[0][i]) >= 0)
hull[0].pop_back();
hull[0].push_back(pts[0][i]); }
for(int i = 0; i < pts[1].size(); ++i) {
while(hull[1].size() > 1 && ccw(hull[1][hull[1].size() - 2], hull[1][hull[1].size() - 1], pts[1][i]) >= 0)
hull[1].pop_back();
hull[1].push_back(pts[1][i]); } }
void get_calipers(void) {
for(p0 = p1 = 0; p0 + 1 < hull[0].size(); ++p0) {
for(; p1 < hull[1].size() && ccw(hull[0][p0], hull[0][p0 + 1], hull[1][p1]) <= 0; ++p1);
if(p1 == hull[1].size())
break; }
for(p1 = 0; p1 + 1 < hull[1].size(); ++p1)
if(ccw(hull[0][p0], hull[1][p1], hull[1][p1 + 1]) <= 0)
break; }
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; }