Here is the link to the problem CodeChef: Practical coding for everyone
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?
