Pagini recente » Cod sursa (job #2918871) | Cod sursa (job #1983302) | Cod sursa (job #1524342) | Cod sursa (job #505375) | Cod sursa (job #3224728)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("oypara.in");
ofstream out("oypara.out");
#define x first
#define y second
typedef pair<long long,long long> point;
vector<point> sus, jos;
vector<point> ls, lj;
int n;
long long id(point a,point b, point c) {
long long sum = b.x * c.y + c.x * a.y + a.x * b.y;
long long dif = a.x * c.y + c.x * b.y + b.x * a.y;
return sum - dif <= 0LL;
}
vector<point> ic(vector<point> p, int s) {
sort(p.begin(), p.end());
if(s)
reverse(p.begin(), p.end());
vector<point> st;
st.push_back(p[0]);
st.push_back(p[1]);
for(int i = 2; i < p.size(); i++) {
for(; st.size() > 1 && id(st[st.size() - 2], st[st.size() - 1], p[i]); st.pop_back());
st.push_back(p[i]);
}
return st;
}
point p1;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
in >> n;
for(int i = 1; i <= n; i++) {
int x, y1, y2;
in >> x >> y1 >> y2;
jos.push_back(make_pair(x, y1));
sus.push_back(make_pair(x, y2));
}
lj = ic(jos, 1);
ls = ic(sus, 0);
for(int i = 0, j = 0; i + 1 < ls.size(); i++) {
for(; id(ls[i], ls[i + 1], lj[j]) && j < lj.size(); ++j);
if(j == lj.size()) {
p1 = ls[i];
break;
}
}
for(int i = 0; i + 1 < lj.size(); i++)
if(id(lj[i], lj[i + 1], p1)) {
out << p1.x << ' ' << p1.y << ' ' << lj[i].x << ' ' << lj[i].y << '\n';
return 0;
}
return 0;
}