Pagini recente » Cod sursa (job #2149655) | Cod sursa (job #533910) | Cod sursa (job #2734220) | Cod sursa (job #312476) | Cod sursa (job #1240323)
#include <fstream>
#include <vector>
#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define LL long long
#define per pair<LL,LL>
using namespace std;
vector <per> sus,jos,ls,lj;
LL det(per a,per b, per c) {return b.x*c.y+c.x*a.y+a.x*b.y-a.x*c.y-c.x*b.y-b.x*a.y<=0LL;}
vector <per> convexa(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 && det(st[st.size()-2],st[st.size()-1],p[i]);st.pop_back());
st.push_back(p[i]);
}
return st;
}
per p1;
int main()
{ ifstream f("oypara.in"); ofstream g("oypara.out");
int n; f>>n;
for(int i=1; i<=n; ++i)
{ int x,y1,y2;
f>>x>>y1>>y2;
jos.push_back(mp(x,y1));
sus.push_back(mp(x,y2));
}
lj=convexa(jos,1); ls=convexa(sus,0);
for(int i=0,j=0;i+1<ls.size();++i)
{ for(;det(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(det(lj[i],lj[i+1],p1))
{ g<<p1.x<<' '<<p1.y<<' '<<lj[i].x<<' '<<lj[i].y;
return 0;
}
}
return 0;
}