Cod sursa(job #2047759)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 25 octombrie 2017 11:13:52
Problema Oypara Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 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 double determ(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    double det=(double)((c.first-a.first)*(b.second-a.second)-(b.first-a.first)*(c.second-a.second));
    return det;
}
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;
    //reverse(st+1,st+vf+1);
    for(;downp<=vf2;downp++)
    {
        while(upp+1<=vf && determ(down[st2[downp]],up[st[upp]],up[st[upp+1]])<0) upp++;
        if(determ(down[st2[downp]],down[st2[downp+1]],up[st[upp]])>=0)
        {
            printf("%d %d ",down[st2[downp]].first,down[st2[downp]].second);
            printf("%d %d\n",up[st[upp]].first,up[st[upp]].second);
            return 0;
        }
    }

    return 0;
}