Pagini recente » Cod sursa (job #1835796) | Cod sursa (job #2086759) | Cod sursa (job #317928) | Cod sursa (job #435096) | Cod sursa (job #2391931)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define x first
#define y second
#define mp make_pair
#define LL long long
using namespace std;
ifstream in("oypara.in");
ofstream out("oypara.out");
typedef pair<LL,LL> per;
int n;
vector<per> sus,jos,ls,lj;
LL id(per a,per b, per c)
{
LL sum=b.x*c.y+c.x*a.y+a.x*b.y;
LL dif=a.x*c.y+c.x*b.y+b.x*a.y;
return sum-dif<=0LL;
}
vector<per> ic(vector<per> p,int s)
{
sort(p.begin(),p.end());
if(s)
reverse(p.begin(),p.end());
vector<per> 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]);
}
//if(s) reverse(st.begin(),st.end());
return st;
}
per p1;
int main()
{
in >> n;
for(int i = 1; i <= n; i++) {
int x, y1, y2;
in >> x >> y1 >> y2;
jos.push_back(mp(x, y1));
sus.push_back(mp(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;
return 0;
}
}
return 0;
}