Can anyone please help me with this convex hull problem?

Here is the link to the problem https://www.codechef.com/ACM16CHN/problems/CHN16B
I have been trying to solve it using convex hull (something which I have learnt recently), that too using Graham-Scan.

Here is my code:

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long

struct point
{
    ll x, y;
};

pair<point,ll> p0;

ll dist_sq(pair<point,ll> p)
{
    return (p.first.x-p0.first.x)*(p.first.x-p0.first.x) + (p.first.y-p0.first.y)*(p.first.y-p0.first.y);
}

bool cmp(pair<point,ll> p, pair<point,ll> q)
{
    ll val = (p.first.y-p0.first.y)*(q.first.x-p0.first.x) - (q.first.y-p0.first.y)*(p.first.x-p0.first.x);
    if(val == 0) return dist_sq(p) < dist_sq(q);
    else return (val < 0) ? true : false;
}

int orientation(pair<point,ll> p, pair<point,ll> q, pair<point,ll> r)
{
    ll val = (q.first.x-p.first.x)*(r.first.y-p.first.y) - (q.first.y-p.first.y)*(r.first.x-p.first.x);
    if(val == 0) return 0; //collinear
    else return (val > 0) ? 1 : 2; // 1->anti-clockwise and 2->clockwise
}

int nextToTop(stack<int>& S)
{
    int p = S.top();
    S.pop();
    int q = S.top();
    S.push(p);

    return q;
}

ll convexHull(vector<pair<point,ll>>& arr, int n)
{
    if(n <= 2)
    {
        ll min_cost = 0;
        rep(i,0,n) min_cost += arr[i].second;

        return min_cost;
    }
    if(n == 3)
    {
        ll min_cost;
        if(orientation(arr[0],arr[1],arr[2]) == 0) min_cost = arr[0].second + arr[2].second;
        else min_cost = arr[0].second + arr[1].second + arr[2].second;

        return min_cost;
    }
    stack<int> v;
    v.push(0);
    v.push(1);
    v.push(2);

    rep(i,3,n)
    {
        while(orientation(arr[nextToTop(v)],arr[v.top()],arr[i]) != 1)
            v.pop();
        v.push(i);
    }

    ll min_cost = 0;
    while(!v.empty())
    {
        min_cost += arr[v.top()].second;
        v.pop();
    }

    return min_cost;
}

int main()
{
    int n;
    cin >> n;
    vector<pair<point,ll>> arr(n);
    rep(i,0,n) cin >> arr[i].first.x >> arr[i].first.y >> arr[i].second;

    ll l = 0;
    rep(i,0,n)
    {
        if((arr[i].first.y < arr[l].first.y)||(arr[i].first.y == arr[l].first.y && arr[i].first.x < arr[l].first.x))
            l = i;
    }
    p0 = arr[l];

    sort(arr.begin(), arr.end(), cmp);

//    for(auto k : arr) cout << k.first.x << " " << k.first.y << "\n";

    cout << convexHull(arr,n) << "\n";

    return 0;
}

I tested the above code on the following sample test case:

9
1 1 3
2 2 5
3 3 8
5 4 4
3 1 2
4 3 6
5 3 4
6 2 3
4 2 5

I got 20 as the answer. On plotting the points on a graphing calculator and then manually finding the convex hull I was able to verify that 20 was the correct answer. But on submitting I got a WA. Can anyone please help me in figuring out the flaw in my code?

@everule1 Please help.

Can you explain why you are finding the convex hull?

Because of:

  1. https://www.youtube.com/watch?v=UUCKvHTP4Gg
  2. https://www.youtube.com/watch?v=bCi7NGw_7oY

The first video mentions this problem at the end, and the second video explains why do we need to find the convex hull.
I thought it would be a nice implementation problem of convex hull using Graham-Scan.

Note: The explanation for this problem begins at 18:56 in the second video.

I know how to do it. The cp - algorithm implementation uses two stacks, so I thought you only found the lower convex hull.

Testcase
7
0 4 8
2 6 0
4 1 0
4 3 1
6 0 6
6 2 4
6 3 7
Correct answer
21
1 Like

Thanks a lot. An AC finally ! :smile: