Pagini recente » Cod sursa (job #1723662) | Cod sursa (job #1987424) | Cod sursa (job #270044) | Cod sursa (job #1171756) | Cod sursa (job #1722025)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 100005;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator <(const Point &o) const { return 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, Top, nUpper, nLower;
Point Stack[N_MAX];
Point Upper[N_MAX];
Point Lower[N_MAX];
int main() {
ifstream f("oypara.in");
ofstream g("oypara.out");
int x, yLower, yUpper;
f >> N;
for(int i = 1; i <= N; i++) {
f >> x >> yLower >> yUpper;
Upper[++nUpper] = Point(x, yUpper);
Lower[++nLower] = Point(x, yLower);
}
sort(Upper + 1, Upper + nUpper + 1);
Stack[1] = Upper[1];
Stack[2] = Upper[2];
Top = 2;
for(int i = 3; i <= nUpper; i++) {
while(Top > 1 && Det(Stack[Top - 1], Stack[Top], Upper[i]) <= 0)
Top--;
Stack[++Top] = Upper[i];
}
nUpper = Top;
for(int i = 1; i <= nUpper; i++)
Upper[i] = Stack[i];
sort(Lower + 1, Lower + nLower + 1);
Stack[1] = Lower[1];
Stack[2] = Lower[2];
Top = 2;
for(int i = 3; i <= nLower; i++) {
while(Top > 1 && Det(Stack[Top - 1], Stack[Top], Lower[i]) >= 0)
Top--;
Stack[++Top] = Lower[i];
}
nLower = Top;
for(int i = 1; i <= nLower; i++)
Lower[i] = Stack[i];
int i, j;
for(i = 1, j = 1; i < nLower; i++) {
while(Det(Lower[i], Upper[j], Upper[j + 1]) <= 0)
j++;
if(Det(Lower[i], Lower[i + 1], Upper[j]) >= 0) {
g << Lower[i].x << " " << Lower[i].y << " " << Upper[j].x << " " << Upper[j].y << "\n";
return 0;
}
}
return 0;
}