Problem Of The Week: Save The Trees

Problem Writer : devuy11243

This week, let's discuss a problem that appeared at the ACM ICPC Asia-Kolkata Onsite Round in 2015, "Save the Trees" - https://www.codechef.com/problems/KOL1509

The summary of the problem statement is as follows - Given an array A of N elements, co-ordinates (A[ i ], A[ j ]) are plotted on a 2D Graph, for all i < j.
You need to find the value equal to twice the area of the boundary of the co-ordinates.
In other words, you need to find the convex hull, and find the area bound by this convex hull in the 2D Graph.
Now, there are standard algorithms to determine a convex hull, given some co-ordinates, but the problem here is to efficiently calculate those co-ordinates.
The reason being, an O(N^2) algorithm is too slow to pass the time limit due to the constraints and so we need to do better. So how do we determine all co-ordinates?
It's a matter of observation. Consider this, let's say you have 3 co-ordinates - (A, X), (A, Y) and (A, Z) (where X<=Y<=Z). Notice the 3 co-ordinate's abscissa (X-coordinates) are all the same, while their Y-coordinates differ. Now among these 3, (A, Y) will surely not be a potential point that lies on the convex hull simply because if it's a potential point lying on the top half of the convex hull, (A, Z) would be the coordinate that would be best chosen instead, and similarly if (A, Y) was a potential point on the convex hull lying on the lower half, it will not be chosen as (A, X) is a better point to place the convex hull on.
Therefore, in general, the coordinates of the upper half of the convex hull would be (A[ i ], max( all elements in A from index i+1 to N ) )
Similarly, the coordinates of the lower half of the convex hull, would correspondingly be (A[ i ], min( all elements in A from index i+1 to N ) )
An example would be -
If the input array was [1, 1, 2, 3]
The total co-ordinates are { (1,1), (1,2), (1,3), (1, 2), (1, 3), (2, 3) }
And the points potentially making the convex hull would be { (1,1), (1,3), (2,3) }
Thus, we can do this effectively by processing elements in reverse order and storing the current maximum/minimum and assigning it to an auxiliary array to the corresponding element.
Now that we have our potential co-ordinates, we still need to find the convex hull as not all the potential points need to lie on the convex hull. (Consider the input [1, 3, 5, 4, 6, 2])
We can do this using an algorithm like Graham's Scan which accomplishes the convex hull processing and generation in O(N logN)
After doing so, the problem has been broken down to solving for just the area of a polygon given their coordinates and this can be solved by leveraging vector cross products or the shoelace formula.
Here is my implementation which follows the above algorithm - care must be taken to use datatypes large enough to hold the final area, else a Wrong Answer penalty is issued.


#include<bits/stdc++.h>
using namespace std;
struct pt{
long long x;
long long y;
};
bool cmp(pt a, pt b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
long long cw(pt a, pt b, pt c){
return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y) < 0;
}
long long ccw(pt a, pt b, pt c){
return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y) > 0;
}
long long getarea(pt a, pt b, pt c){
return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}
vector<pt> ch(vector<pt> a){
pt p1 = a[0];
pt p2 = a.back();
vector<pt> up;
vector<pt> down;
up.push_back(p1);
down.push_back(p1);
for(long long i=0;i<a.size();i++){
if(i==a.size() - 1|| cw(p1, a[i], p2)){
while(up.size()>=2 && !cw(up[up.size()-2], up[up.size()-1], a[i]))up.pop_back();
up.push_back(a[i]);
}
if(i==a.size() - 1|| ccw(p1, a[i], p2)){
while(down.size()>=2 && !ccw(down[down.size()-2], down[down.size()-1], a[i]))down.pop_back();
down.push_back(a[i]);
}
}
vector<pt> ans;
for(long long i=0;i<up.size();i++)ans.push_back(up[i]);
for(long long i=down.size()-2;i>=0;i--)ans.push_back(down[i]);
return ans;
}
int main(){
long long t;
std::ios_base::sync_with_stdio(0);
cin>>t;
while(t--){
long long n;
cin>>n;
vector<long long> A(n);
vector<long long> mx(n);
vector<long long> mn(n);
for(long long i =0 ;i<n;i++){
cin>>A[i];
mx[i] = 0;
mn[i] = 1e9;
}
mx[n-1] = A[n-1];
mn[n-1] = A[n-1];
for(long long i=n-2;i>=0;i--){
mx[i] = max(A[i+1], mx[i+1]);
mn[i] = min(A[i+1], mn[i+1]);
}
vector<pt> in;
for(long long i=0;i<n-1;i++){
pt temp;
temp.x = A[i];
temp.y = mx[i];
in.push_back(temp);
}
for(long long i=0;i<n-2;i++){
pt temp;
temp.x = A[i];
temp.y = mn[i];
in.push_back(temp);
}
sort(in.begin(), in.end(), cmp);
vector<pt> hull = ch(in);
long long area = 0;
for(long long i=1;i<hull.size();i++)area += getarea(hull[0], hull[i], hull[(i+1)%hull.size()]);
cout<<abs(area)<<"\n";
}
}