Pagini recente » Cod sursa (job #2624127) | Cod sursa (job #2117292) | Cod sursa (job #2735962) | Cod sursa (job #3275182) | Cod sursa (job #600468)
Cod sursa(job #600468)
# include <algorithm>
# include <cstdio>
# include <bitset>
# include <vector>
using namespace std;
# define x first
# define y1 second.first
# define y2 second.second
# define y second
typedef pair <int, int> PR;
const char *FIN = "oypara.in", *FOU = "oypara.out";
const int MAX = 100005;
inline long long check (PR P3, PR P1, PR P2) {
return 1LL * P3.x * (P1.y - P2.y) + 1LL * P3.y * (P2.x - P1.x) - 1LL * P1.x * (P1.y - P2.y) - 1LL * P1.y * (P2.x - P1.x);
}
pair <int, PR> seg[MAX];
vector <PR> sus, jos;
int N;
inline int in (PR A, PR B, PR C) {
return 1LL * (A.y - B.y) * C.x + 1LL * (B.x - A.x) * C.y + (1LL * A.x * B.y) - (1LL * B.x * A.y) < 0;
}
vector <PR> convex_hull (vector <PR> &V) {
vector <int> stk;
vector <PR> P;
bitset <MAX> viz;
stk.push_back (0), stk.push_back (1), viz[1] = 1;
for (int i = 2, wh = 1; viz[0] == 0; stk.push_back (i), viz[i] = 1) {
for (; viz[i] ; i += wh = (i == N - 1 ? -1 : wh)) ;
for (; stk.size () > 1 && in (V[*(stk.end () - 2)], V[stk.back ()], V[i]); viz[stk.back ()] = 0, stk.pop_back ());
}
for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
P.push_back (V[stk[i]]);
stk.clear ();
return P;
}
inline int doit (int semn) {
for (size_t i = 0, j = jos.size (), wh = 0; i < j; ++i) {
for (int aux = 0; true; wh = aux) {
aux = wh == sus.size () - 1 ? 0 : wh + 1;
if (check (sus[aux], jos[i], sus[wh]) * semn >= 0) break;
}
for (int aux = 0; true; wh = aux) {
aux = wh == 0 ? sus.size () - 1 : wh - 1;
if (check (sus[aux], jos[i], sus[wh]) * semn >= 0) break;
}
int aux1 = i == jos.size () - 1 ? 0 : i + 1;
int aux2 = i == 0 ? jos.size () - 1 : i - 1;
if (check (jos[aux1], jos[i], sus[wh]) * semn <= 0 && check (jos[aux2], jos[i], sus[wh]) * semn <= 0) {
fprintf (fopen (FOU, "w"), "%d %d %d %d", jos[i].x, jos[i].y, sus[wh].x, sus[wh].y);
return 0;
}
}
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d", &N);
for (int i = 0; i < N; ++i)
scanf ("%d %d %d", &seg[i].x, &seg[i].y1, &seg[i].y2);
sort (seg, seg + N);
for (int i = 0; i < N; ++i) {
jos.push_back (make_pair (seg[i].x, seg[i].y1));
sus.push_back (make_pair (seg[i].x, seg[i].y2));
}
jos = convex_hull (jos), sus = convex_hull (sus);
if (doit (1)) doit (-1);
}