Cod sursa(job #2049125)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 26 octombrie 2017 21:22:47
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<bits/stdc++.h>
#define maxN 200005
using namespace std;
int n,st[maxN],st2[maxN],vf,vf2;
pair<int,int> up[maxN],down[maxN];
vector<pair<int,int> > uppoints,downpoints;
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 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;
    }
    for(int i=1;i<=vf;i++)
        uppoints.push_back(up[st[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);
    vf=0;
    st[++vf]=1;
    st[++vf]=2;
    for(int i=3;i<=n;i++)
    {
        if(vf>=2 && !comp(down[st[vf-1]],down[st[vf]],down[i])) vf--;
        st[++vf]=i;
    }
    for(int i=1;i<=vf;i++)
    {
        downpoints.push_back(down[st[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=0,downp=0;
    int i=0;
    int sz=downpoints.size();
    for(i=0;i<sz;upp++)
    {
     //   if(upp>vf) upp-=vf;
        while(upp<(int)uppoints.size() && !comp(uppoints[upp],uppoints[upp+1],downpoints[i])) i++;
    }
    while(comp(downpoints[downp],downpoints[downp+1],uppoints[upp-1])) downp++;
    printf("%d %d ",uppoints[upp-1].first,uppoints[upp-1].second);
    printf("%d %d\n",downpoints[downp].first,downpoints[downp].second);


    return 0;
}