Pagini recente » Cod sursa (job #2001550) | Cod sursa (job #3228046) | Cod sursa (job #2074780) | Cod sursa (job #455842) | Cod sursa (job #1805609)
#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].rbegin(), pts[0].rend()); // hai sa nu mai vorbim despre cum nu stiu eu sa bag rotating callipers
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) { // mda...
for(p0 = p1 = 0; p1 + 1 < hull[1].size(); ++p1) {
for(; p0 < hull[0].size() && ccw(hull[1][p1], hull[1][p1 + 1], hull[0][p0]) <= 0; ++p0);
if(p0 == hull[0].size())
break; }
for(p0 = 0; p0 + 1 < hull[0].size(); ++p0)
if(ccw(hull[0][p0], hull[0][p0 + 1], hull[1][p1]) <= 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", hull[0][p0].x, hull[0][p0].y , hull[1][p1].x, hull[1][p1].y); //facepalm
return 0; }