Cod sursa(job #2047767)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 25 octombrie 2017 11:27:16
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
int n,st[maxN],st2[maxN],vf,vf2;
pair<int,int> up[maxN],down[maxN];
inline long long determ(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    long long det=(long long)((1LL*(c.first-a.first))*(1LL*(b.second-a.second))-(1LL*(b.first-a.first))*
                              (1LL*(c.second-a.second)));
    return det;
}
inline bool comp(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    return 1LL*(a.first-c.first)*(b.second-c.second)>1LL*(a.second-c.second)*(b.first-c.first);
}
inline double Dist(pair<int,int> a,pair<int,int> b)
{
    double d=(a.second-b.second)*(a.second-b.second)+(a.first-b.first)*(a.first-b.first);
    d=sqrt((double)d);
    return d;
}

inline bool cmp(pair<int,int> a,pair<int,int> b)
{
    double det=determ(up[1],a,b);
    if(det==0) return Dist(up[1],a)<Dist(up[1],b);
    return det>0;
}
inline bool cmp2(pair<int,int> a,pair<int,int> b)
{
    double det=determ(down[1],a,b);
    if(det==0) return Dist(down[1],a)<Dist(down[1],b);
    return det>0;
}
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]);
    st[++vf]=1;
    sort(up+2,up+n+1,cmp);
    st[++vf]=2;
    for(int i=3;i<=n;i++)
    {
        if(vf>=2 && determ(up[st[vf-1]],up[st[vf]],up[i])<0) vf--;
        st[++vf]=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]);
    st2[++vf2]=1;
    sort(down+2,down+n+1,cmp2);
    st2[++vf2]=2;
    for(int i=3;i<=n;i++)
    {
        if(vf>=2 && determ(down[st2[vf2-1]],down[st2[vf2]],down[i])<0) vf2--;
        st2[++vf2]=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,ya};
        down[i]={x,yb};
    }
    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=1,downp=1;
    int i;
    for(i=1;i<=vf2;upp++)
    {
        while(i<=vf2 && !comp(up[st[upp]],up[st[upp+1]],down[st2[i]])) i++;
    }
    while(comp(down[st2[downp]],down[st2[downp+1]],up[st[upp-1]])) downp++;
    printf("%d %d ",down[st2[downp]].first,down[st2[downp]].second);
    printf("%d %d\n",up[st[upp-1]].first,up[st[upp-1]].second);

    return 0;
}