BSHEEP-Build the Fence

Build the Fence 

Given below code is for bsheep spoj or build the fence spoj.

Hint:- Simple implementation of any O(N log N) algorithm for  Convex Hull. 

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 22 October 2015 (Thursday) 09:33
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
class point{
public:
    int x , y , pos;
    point(){};
    point(int a , int b , int c){x = a , y = b , pos = c;}
    double distance(point &a){
        int dx = a.x - x;
        int dy = a.y - y;
        return sqrt(dx*dx + dy*dy);
    }
    bool operator != (point &a){
        if(a.x != x || a.y != y)
            return true;
        return false;
    }
};
bool cmp(const point &a , const point &b){
    return a.y == b.y ? (a.x == b.x ? a.pos < b.pos : a.x < b.x ): a.y < b.y;
}
int orientation( point P , point Q , point R ){
    return  ( Q.x - P.x ) * ( R.y - P.y ) - ( R.x - P.x ) * ( Q.y - P.y );
}
void convex_hull(vector<point> &p , vector<point> &upper , vector<point> &lower){
    sort(p.begin() , p.end() , cmp);
    int k = 1;
    for(int i = 1 ; i < p.size() ; i++)
        if(p[i-1] != p[i])
            p[k++] = p[i];
    p.resize(k);
    int sz = 2*k;
    upper.resize(sz);
    lower.resize(sz);
    int j = 0 ;
    k = 0;
    for(int i = 0 ; i < p.size() ; i++){
        while(j >= 2 && orientation(lower[j-2] , lower[j-1] , p[i]) <= 0)
            j--;
        while(k >=2 && orientation(upper[k-2] , upper[k-1] , p[i]) >= 0)
            k--;
        lower[j++] = p[i];
        upper[k++] = p[i];
    }
    lower.resize(j);
    upper.resize(k);
}
int main(){
    
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        vector<point> v;
        int x , y;
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d",&x , &y);
            v.pb(point(x , y , i+1));
        }
        vector<point> lower , upper;
        convex_hull(v , upper , lower);
        for(int i = upper.size() - 2 ; i > 0 ; i--)
            lower.pb(upper[i]);
        double dist = 0.0;
        for(int i = 1 ; i < lower.size() ; i++)
            dist += lower[i-1].distance(lower[i]);
        dist += lower[lower.size() -1].distance(lower[0]);
        printf("%.2lf\n", dist);
        for(int i = 0 ; i < lower.size() ; i++)
            printf("%d ", lower[i].pos);
        printf("\n");
    }
    
    return 0;
}

WPC5E-Galaxy distances

Galaxy distances

Given below c++ code is for wpc5e spoj or galaxy distances spoj.

Hint :- 

1-> Construct a convex hull from given set of point.(N log N)

2-> Now the points having maximum distance will lie on boundary of convex hull.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 17 October 2015 (Saturday) 18:16
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pll pair < long long , long long >
#define ll long long
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
void pr_uint(unsigned long long  n) {
    if (n / 10 != 0)
        pr_uint(n / 10);
    putchar_unlocked((n % 10) + '0');
}

void pr_int(long long n) {
    if (n < 0) {
        putchar_unlocked('-');
        n = -n;
    }
    pr_uint((unsigned long long) n);
}
long long orientation(pll P,pll Q,pll R){
    return  (Q.first-P.first)*(R.second-P.second)-(R.first-P.first)*(Q.second-P.second);
}
int slope_compare(pll &a , pll &b , pll &c , pll &d){
    if((b.second - a.second)*(d.first - c.first) > (b.first - a.first)*(d.second - c.second))
        return 1;
    return 0;
}
void convex_hull(vector<pll > &P,vector<pll > &l,vector<pll > &u){
    int j=0,k=0,n=P.size();
    sort(P.begin(),P.end());
    u.resize(2*n);
    l.resize(2*n);
    for(int i=0;i<n;i++)
    {
        while(j>=2 && orientation(l[j-2],l[j-1],P[i])<=0)
            j--;
        while(k>=2 && orientation(u[k-2],u[k-1],P[i])>=0)
            k--;
        l[j++]=P[i];
        u[k++]=P[i];
    }
    u.resize(k);
    l.resize(j);
}
long long Dist(pll P ,pll Q){
    return abs(P.first*P.first - Q.first*Q.first)+abs(P.second*P.second - Q.second*Q.second);
}
int main()
{
    int t;
    scanint(t);
    while(t--)
    {
        vector<pll >v,u,l;
        int n;
        scanint(n);
        int k1;
        for(int i=0;i<n;i++){
            scanint(k1);
            v.push_back(make_pair(i+1,k1));
        }
        if(n==1){
            printf("0\n");
            continue;
        }
        convex_hull(v,l,u);//conpute convex hull for set of points .
        int i = 0 , j = l.size() -1;
        ll ans = 0;
        l.insert(l.end() , u.begin() , u.end());
        for(int i = 0 ; i < l.size() ; i++){ // Brute Force to find points having maximum distance.
         for(int j = 0 ; j < l.size() ; j++){
          ans = max(ans , Dist(l[i] , l[j]));
         }
        }
        pr_int(ans);
        putchar_unlocked('\n');
    }
}