Cod sursa(job #1821098)

Utilizator LucianTLucian Trepteanu LucianT Data 2 decembrie 2016 16:57:48
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#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;
}