Pagini recente » Cod sursa (job #1367755) | Cod sursa (job #369289) | Cod sursa (job #1402273) | Cod sursa (job #1076508) | Cod sursa (job #1722280)
#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 {
if(x == o.x) return y < o.y;
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, 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");
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);
}
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], Upper[U], Lower[D + 1]) < 0) {
g << Lower[D].x << " " << Lower[D].y << " " << Upper[U].x << " " << Upper[U].y << "\n";
break;
}
D++;
}
return 0;
}