Pagini recente » Cod sursa (job #3179674) | Cod sursa (job #2143426) | Cod sursa (job #2300594) | Cod sursa (job #3184642) | Cod sursa (job #2051096)
#include <cstdio>
#include <cctype>
#include <algorithm>
FILE *fin = fopen("oypara.in", "r"), *fout = fopen("oypara.out", "w");
#define BUF_SIZE 1 << 17
int pos = BUF_SIZE;
char buf[BUF_SIZE];
inline char nextch() {
if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
return buf[pos++];
}
inline int read() {
char ch;
while (!isdigit(ch = nextch()));
int x = ch - '0';
while (isdigit(ch = nextch())) x = 10 * x + ch - '0';
return x;
}
#define MAXN 100000
struct myc {
int x, y;
inline bool operator < (const myc &u) const {
return x < u.x;
}
} u[MAXN + 1], v[MAXN + 1];
int k, m, st[MAXN + 1];
inline long long arie(myc a, myc b, myc c) {
return 1LL * a.x * b.y - 1LL * a.y * b.x + 1LL * b.x * c.y - 1LL * b.y * c.x + 1LL * c.x * a.y - 1LL * c.y * a.x;
}
inline void lowerEnvelope(int n) {
std::sort(u + 1, u + n + 1);
int vf = 0;
for (int i = 1; i <= n; i++) {
while (vf > 1 && arie(u[st[vf - 1]], u[st[vf]], u[i]) <= 0)
vf--;
st[++vf] = i;
}
for (int i = 1; i <= vf; i++)
u[i] = u[st[i]];
k = vf;
}
inline void upperEnvelope(int n) {
std::sort(v + 1, v + n + 1);
int vf = 0;
for (int i = 1; i <= n; i++) {
while (vf > 1 && arie(v[st[vf - 1]], v[st[vf]], v[i]) >= 0)
vf--;
st[++vf] = i;
}
for (int i = 1; i <= vf; i++)
v[i] = v[st[i]];
m = vf;
}
inline bool bun(myc a, myc b) {
if (a.x > b.x) std::swap(a, b);
for (int i = 1; i <= k; i++)
if (arie(a, b, u[i]) < 0)
return 0;
for (int i = 1; i <= m; i++)
if (arie(a, b, v[i]) > 0)
return 0;
return 1;
}
int main() {
int n = read();
for (int i = 1; i <= n; i++) {
v[i].x = u[i].x = read();
v[i].y = read();
u[i].y = read();
}
lowerEnvelope(n);
upperEnvelope(n);
int r = 1;
for (int i = 2; i <= k; i++)
if (u[i].y < u[r].y)
r = i;
int p = r + 1;
if (r == k) p = r - 1;
int q = 1;
for (int i = 2; i <= m; i++)
if (arie(u[r], v[q], v[i]) < 0)
q = i;
if (bun(u[r], u[p])) fprintf(fout, "%d %d %d %d\n", u[r].x, u[r].y, u[p].x, u[p].y);
else if (bun(u[r], v[q])) fprintf(fout, "%d %d %d %d\n", u[r].x, u[r].y, v[q].x, v[q].y);
else return 1;
return 0;
}