Cod sursa(job #2048476)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 26 octombrie 2017 00:45:17
Problema Oypara Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 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))*(1LL*(b.second-c.second))>(1LL*(a.second-c.second))*(1LL*(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]);

    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;
    }

}

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);
    st2[++vf2]=1;
    st2[++vf2]=2;
    for(int i=3;i<=n;i++)
    {
        if(vf2>=2 && !comp(down[st2[vf2-1]],down[st2[vf2]],down[i])) 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,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=1,downp=1;
    int i=0;
    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;
}