Pagini recente » Cod sursa (job #1803035) | Cod sursa (job #1706697) | Cod sursa (job #781978) | Cod sursa (job #1088231) | Cod sursa (job #821958)
Cod sursa(job #821958)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#define x first
#define y second
using namespace std;
typedef pair<double, double> Point;
const int MaxN = 100005;
const double Eps = 1e-12;
vector<Point> Up, Down;
int NSegments;
bool Solution;
Point S1, S2;
inline double Det(Point P1, Point P2, Point P3) {
return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P1.y*P2.x - P2.y*P3.x - P3.y*P1.x;
}
vector<Point> ConvexHull(vector<Point> Points) {
int N = Points.size(), K = 0;
vector<int> Stack(N+2); bitset<MaxN> Used;
sort(Points.begin(), Points.end());
Stack[++K] = 0;
for (int i = 1, p = 1; i >= 0; i += (p = (i == N-1 ? -p : p))) {
if (Used[i])
continue;
while (K > 1 && Det(Points[Stack[K-1]], Points[Stack[K]], Points[i]) <= -Eps)
Used[Stack[K--]] = false;
Used[Stack[++K] = i] = true;
}
vector<Point> Hull(K);
for (int i = 0; i < K; ++i)
Hull[i] = Points[Stack[i+1]];
return Hull;
}
void FindLine(vector<Point> P1, vector<Point> P2, bool Side) {
int N = P1.size()-1, M = P2.size()-1;
for (int i = 0, j = 0; i < N; ++i) {
if (P1[i] < P1[i+1] != Side)
continue;
int Steps = 0;
while (Steps <= M && Det(P1[i], P1[i+1], P2[j]) <= Eps)
j = (j+1)%M, ++Steps;
if (Steps >= M) {
Solution = true, S1 = P1[i], S2 = P1[i+1];
return;
}
}
}
void Solve() {
vector<Point> UpHull = ConvexHull(Up);
vector<Point> DownHull = ConvexHull(Down);
FindLine(DownHull, UpHull, false);
FindLine(UpHull, DownHull, true);
}
void Read() {
freopen("oypara.in", "r", stdin);
scanf("%d", &NSegments);
for (int i = 0; i < NSegments; ++i) {
int x, y1, y2; scanf("%d %d %d", &x, &y1, &y2);
Up.push_back(Point(x, max(y1, y2)));
Down.push_back(Point(x, min(y1, y2)));
}
}
void Print() {
freopen("oypara.out", "w", stdout);
printf("%.0lf %.0lf %.0lf %.0lf\n", S1.x, S1.y, S2.x, S2.y);
}
int main() {
Read();
Solve();
Print();
return 0;
}