cover
SRM

Problem Of The Week - Convex Hulls And Geometry


Aditya_RameshOctober 10, 2018


This week, let's analyze the Division 1 Level 3 problem from SRM 249 - CultureGrowth.


The summary of the problem is as follows -


Given the X-Y coordinates of some organisms, and given that if there's an organism at (x1, y1) and another at (x2, y2), there will be an organism soon at ((x1+x2)/2, (y1+y2)/2),


Find the area that the organisms enclose in order to calculate how many there are.


Now, let's formalize this.


Initially, we have some points on an XY plane. Every iteration, new points appear (the medians of every pair of points). Eventually, all points within some final polygon will be filled with points, as the median of every pair generates a new point at that location.


Our task is to find the area enclosed by this polygon.


Now, the shoelace formula (or Gauss' Area formula) allows us to calculate the area of an N-sided polygon in O(N), given the coordinates of the edges.


The shoelace formula is as follows -

image1


One can also find the area of an N-sided polygon by leveraging vector mathematics, by using the concept of vector cross product, which works by triangulating the polygon and adding up the individual triangular areas to calculate the area of the whole polygon.


The problem then reduces to identifying the boundary points of the final polygon, as after this we can calculate the area.


So how would we do that? By determining the convex hull of the given points. Graham's Scan is one of multiple algorithms that allows us to do this in linearithmic time (N logN).


The correctness in this lies in the fact that a convex hull determines the boundary points that when connected enclose all other points, by forming a convex polygon.


Thus, by determining the convex hull of our points, we determine all the boundary organisms that contribute in forming the edges.


Thus, to summarize -

  • Determine the convex hull

  • Find the area of the polygon generated by the points of the convex hull


The fastest implementation of this was in C++, by sean_henderson at a little over 4 minutes and 30 seconds.