Pagini recente » Cod sursa (job #2813976) | Cod sursa (job #2028124) | Cod sursa (job #2865487) | 487531 | Cod sursa (job #2049123)
#include<bits/stdc++.h>
#define maxN 200005
using namespace std;
int n,st[maxN],st2[maxN],vf,vf2;
pair<int,int> up[maxN],down[maxN];
vector<pair<int,int> > uppoints,downpoints;
inline bool comp(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
return (1LL*(a.first-c.first))*(1LL*(b.second-c.second))>(1LL*(a.second-c.second))*(1LL*(b.first-c.first));
}
inline void UpConvexHull()
{
// int best=1;
//for(int i=2;i<=n;i++)
//{
// if(up[i].first<up[best].first || (up[i].first==up[best].first && up[i].second<up[best].second)) best=i;
//}
//swap(up[1],up[best]);
sort(up+1,up+n+1);
st[++vf]=1;
st[++vf]=2;
for(int i=3;i<=n;i++)
{
if(vf>=2 && !comp(up[st[vf-1]],up[st[vf]],up[i])) vf--;
st[++vf]=i;
}
for(int i=1;i<=vf;i++)
uppoints.push_back(up[st[i]]);
}
inline void DownConvexHull()
{
// int best=1;
// for(int i=2;i<=n;i++)
// {
// if(down[i].first<down[best].first || (down[i].first==down[best].first && down[i].second<down[best].second)) best=i;
// }
// swap(down[1],down[best]);
sort(down+1,down+n+1);
reverse(down+1,down+n+1);
vf=0;
st[++vf]=1;
st[++vf]=2;
for(int i=3;i<=n;i++)
{
if(vf>=2 && !comp(down[st[vf-1]],down[st[vf]],down[i])) vf--;
st[++vf]=i;
}
for(int i=1;i<=vf;i++)
{
downpoints.push_back(down[st[i]]);
}
}
inline int Prev(int x)
{
if(x>1) return x-1;
return vf2;
}
int x,ya,yb;
int main()
{
freopen("oypara.in","r",stdin);
freopen("oypara.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&ya,&yb);
up[i]={x,yb};
down[i]={x,ya};
}
UpConvexHull();
DownConvexHull();
/*int pos=1;
for(int i=1;i<=vf;i++)
cerr<<up[st[i]].first<<' '<<up[st[i]].second<<'\n';
cerr<<'\n';
for(int i=1;i<=vf2;i++)
cerr<<down[st2[i]].first<<' '<<down[st2[i]].second<<'\n';*/
int upp=0,downp=0;
int i=0;
int sz=downpoints.size();
for(i=0;i<sz;upp++)
{
// if(upp>vf) upp-=vf;
while(i<sz && !comp(uppoints[upp],uppoints[upp+1],downpoints[i])) i++;
}
while(comp(downpoints[downp],downpoints[downp+1],uppoints[upp-1])) downp++;
printf("%d %d ",uppoints[upp].first,uppoints[upp].second);
printf("%d %d\n",downpoints[downp].first,downpoints[downp].second);
return 0;
}