MGCSTAT - Editorial - TWZT20TS

editorial
, ,
1

PROBLEM LINK:

Practice

Author: Vishal Sharma
Tester: Piyush
Editorialist: Vishal Sharma

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Geometry, Convex Hull

PROBLEM:

Given the positions of statues, (x,y) Use a magic rope to create a fence around all the statues such that all the statues are enclosed.

QUICK EXPLANATION

Find the Convex hull of the coordinates and sort the values. Also take care of repeated values.
Ref: https://algorithmist.com/wiki/Gift_wrapping

EXPLANATION

Gift wrapping algorithm is very simple. We start with the leftmost point among the given set of points and try to wrap up all the given points considering the boundary points in counterclockwise direction.
This means that for every point p considered, we try to find out a point q, such that this point q is the most counterclockwise relative to p than all the other points.
For checking this, we make use of orientation() function in the current implementation. This function takes three arguments p, the current point added in the hull; q, the next point being considered to be added in the hull; r, any other point in the given point space. This function returns a negative value if the point q is more counterclockwise to p than the point r.

To computer orientation we used slope.
Slope of line segment (p1, p2): m1 = \frac{(y2 - y1)}{(x2 - x1)}

Slope of line segment (p2, p3): m2 = \frac{(y3 - y2)}{(x3 - x2)}

If m1 > m2, the orientation is clockwise (right turn)
Using above values of σ and τ, we can conclude that, the orientation depends on sign of below expression: (y2 - y1)*(x3 - x2) - (y3 - y2)*(x2 - x1)
Above expression is negative when m1 < m2, i.e., counterclockwise and when m1==m2 they are co-linear.
Steps:

  1. Initialize p as leftmost point.
  2. Do following while we don’t come back to the first (or leftmost) point.
    ……a) The next point q is the point such that the triplet (p, q, r) is counterclockwise/co-linear for any other point r.
    ……b) next[p] = q (Store q as next of p in the output convex hull).
    ……c) p = q (Set p as q for next iteration).

Time Complexity: O(M∗N)

For every point on the hull we examine all the other points to determine the next point. Here N is number of input points and M is number of output or hull points (M \leq N).

Space complexity : O(M)

List hull grows upto size M.

SOLUTION:

Solution 
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define ll int
#define ull unsigned long long
#define endl "\n"

struct point { 
    ll x, y; 

    bool operator<(const point& rhs) const {
    if(x == rhs.x) return y<rhs.y;
    return x < rhs.x; 
    }

    bool operator==(const point& rhs) const {
        return x==rhs.x && y==rhs.y;
    }
}; 

ll min(ll a, ll b) {return a<b?a:b;}
ll max(ll a, ll b) {return a>b?a:b;}


int orientation(point p, point q, point r) { 
    ll val = (q.y - p.y) * (r.x - q.x) - 
            (q.x - p.x) * (r.y - q.y); 

    if (val == 0) return 0;  // colinear 
    return (val > 0)? 1: 2; // clock or counterclock wise 
} 

ll distance(point a, point b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

// Returns convex hull of a set of n points. 
vector<point> convexHull(vector<point> points) { 
    int n = points.size();
    // There must be at least 3 points 
    if (n < 3) return {}; 

    // Initialize Result 
    vector<point> hull; 

    // Find the leftmost point 
    int l = 0; 
    for (int i = 1; i < n; i++) 
        if (points[i].x < points[l].x) 
            l = i; 
    
    int p = l, q; 
    set<point> ret;
    do
    { 
        hull.push_back(points[p]); 
        ret.insert(points[p]);
        set<point> temp;
        q = (p+1)%n; 

        for (int i = 0; i < n; i++) 
        { 
            int o = orientation(points[p], points[i], points[q]);
            if (o == 2) {
                temp.clear();
                q=i;
                temp.insert(points[i]);
            }
            else if(o==0) {
                temp.insert(points[i]);
            }
        } 
        
        for(auto i:temp) {
            ret.insert(i);
            hull.push_back(i);
        } 
        p=q;

    } while (p != l);  
    return hull;
} 

void solve() {
    int n;
    cin>>n;
    vector<point> points(n);
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        points[i].x=x;
    }
    for(int i=0;i<n;i++) {
        int y;
        cin>>y;
        points[i].y = y;
    }


    auto hull = convexHull(points);

    sort(hull.begin(), hull.end());
    set<point> ret;
    for(auto i: hull) {
        ret.insert(i);
    }

    for(auto i: ret) {
        cout<<i.x<<" "<<i.y<<endl;
    }

}

int32_t main() {
    solve();
    return 0;
}
1 Like