Pagini recente » Cod sursa (job #1781924) | Cod sursa (job #576914) | Cod sursa (job #812268) | Cod sursa (job #2749063) | Cod sursa (job #1821098)
#include <bits/stdc++.h>
#define maxN 100005
#define pII pair<int,int>
using namespace std;
vector<pair<int,int> >upPoints,downPoints;
vector<pair<int,int> >upHull,downHull;
int n,i,j,x,yup,ydown;
int up,down;
int stk[maxN],top;
bool det(pII a,pII b,pII c)
{
return 1LL*(a.first-c.first)*(b.second-c.second)>1LL*(a.second-c.second)*(b.first-c.first);
}
void upConvexHull()
{
sort(upPoints.begin(),upPoints.end());
top=0;
stk[++top]=0;
stk[++top]=1;
for(int i=2;i<(int)upPoints.size();i++)
{
while(top>=2 && !det(upPoints[stk[top-1]],upPoints[stk[top]],upPoints[i]))
top--;
stk[++top]=i;
}
for(int i=1;i<=top;i++)
upHull.push_back(upPoints[stk[i]]);
}
void downConvexHull()
{
sort(downPoints.begin(),downPoints.end());
reverse(downPoints.begin(),downPoints.end());
top=0;
stk[++top]=0;
stk[++top]=1;
for(int i=2;i<(int)downPoints.size();i++)
{
while(top>=2 && !det(downPoints[stk[top-1]],downPoints[stk[top]],downPoints[i]))
top--;
stk[++top]=i;
}
for(int i=1;i<=top;i++)
downHull.push_back(downPoints[stk[i]]);
}
int main()
{
freopen("oypara.in","r",stdin);
freopen("oypara.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d %d %d",&x,&ydown,&yup),
upPoints.push_back(make_pair(x,yup)),
downPoints.push_back(make_pair(x,ydown));
upConvexHull();
downConvexHull();
for(i=0;i<(int)downHull.size();up++)
while(i<(int)downHull.size() && !det(upHull[up],upHull[up+1],downHull[i]))
i++;
while(det(downHull[down],downHull[down+1],upHull[up-1]))
down++;
printf("%d %d ",upHull[up-1].first,upHull[up-1].second);
printf("%d %d",downHull[down].first,downHull[down].second);
return 0;
}