Pagini recente » Cod sursa (job #372313) | Cod sursa (job #66229) | Cod sursa (job #2942273) | Cod sursa (job #2127103) | Cod sursa (job #1722300)
#include <fstream>
#include <algorithm>
using namespace std;
const int N_MAX = 100005;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
inline bool operator <(const Point &o) const { return (x == o.x ? y < o.y : x < o.x); }
};
int64_t Det(const Point &A, const Point &B, const Point &C) {
return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (C.x - A.x) * (B.y - A.y);
}
int N, nUpper, nLower;
Point Upper[N_MAX];
Point Lower[N_MAX];
void getConvex(Point P[], int &Size, bool Order) {
Point Stack[N_MAX];
int Top;
sort(P+1, P+Size+1);
if(Order == 1) reverse(P+1, P+Size+1);
Stack[1] = P[1];
Stack[2] = P[2];
Top = 2;
for(int i = 3; i <= Size; i++) {
while(Top > 1 && Det(Stack[Top - 1], Stack[Top], P[i]) >= 0LL) Top--;
Stack[++Top] = P[i];
}
Size = Top;
for(int i = 1; i <= Size; i++)
P[i] = Stack[i];
}
int main() {
ifstream f("oypara.in");
ofstream g("oypara.out");
f >> N;
for(int i = 1, x, yD, yU; i <= N; i++) {
f >> x >> yD >> yU;
Upper[++nUpper] = Point(x, yU);
Lower[++nLower] = Point(x, yD);
}
getConvex(Upper, nUpper, 1);
getConvex(Lower, nLower, 0);
int U = 1, D = 1;
while(D < nLower) {
while(U < nUpper && Det(Lower[D], Upper[U], Upper[U + 1]) < 0LL)
U++;
if(Det(Lower[D], Lower[D + 1], Upper[U]) >= 0) {
g << Lower[D].x << " " << Lower[D].y << " " << Upper[U].x << " " << Upper[U].y << "\n";
break;
}
D++;
}
return 0;
}