SRM 641, D1, 250-Pointer (TrianglesContainOrigin)

James S. Plank

Tue Sep 5 12:00:18 EDT 2017
My writeup of this problem is in presentation form. You can find it here.

Solution

My solution is in Solution.cpp. I've included it below as well -- you should walk through the presentation in order to understand the solution.

/* Topcoder SRM 641, D1, 250-Pointer (TrianglesContainOrigin)
   James S. Plank
   Tue Sep  5 12:05:39 EDT 2017
 */

#include <vector>
#include <cmath>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class TrianglesContainOrigin {
  public:
    long long count(vector <int> x, vector <int> y);
};


long long TrianglesContainOrigin::count(vector <int> x, vector <int> y)
{
  int i;
  map <double, int> M;        // Map of points.  Key = angle from origin.  Val = ordering.
           
  double dx, dy;              // The rest of these are temporary.
  double angle, d;
  double pi;
  long long rv;
  map <double, int>::iterator mit1, mit2, mit3, mit4;

  pi = acos(-1.0);            // This is my reliable way of calculating PI.

  /* For each point, figure out its angle from the origin, using acos.  If the
     point's Y value is negative, then the angle is (2*PI - acos(x/hypotenuse)). */

  for (i = 0; i < x.size(); i++) {
    dx = x[i];
    dy = y[i];
    d = sqrt(dx*dx + dy*dy);
    angle = acos(dx/d);
    if (dy < 0) angle = 2 * pi - angle;

    /* We insert each point twice into the map -- once with its angle, and once with 
       its angle plus 2*PI.  The reason for this is that if we do it this way, we 
       don't have to worry about wrapping around 360 degrees, or that M.upper_bound()
       will return M.end(). */

    M[angle] = 0;
    M[angle+2*pi] = 0;
  }

  /* Add the val fields -- these are the orders of the angles. */

  i = 0;
  for (mit1 = M.begin(); mit1 != M.end(); mit1++) {
    mit1->second = i;
    i++;
  }

  /* Here's our main enumeration -- mit1 points to the first point, and mit2
     points to the second point, which has to be < 180 degrees from the first point.
     mit3 is the first point within 180 degrees of the first point, and mit4 is the
     first point that is > 180 degrees away from the second point.  Since we've inserted
     all of the points twice, we don't have to worry about upper_bound() returning
     M.end().  Everything just works... */

  rv = 0;
  for (mit1 = M.begin(); mit1->first < 2*pi; mit1++) {
    mit3 = M.upper_bound(mit1->first + pi);
    mit2 = mit1;
    for (mit2++; mit2->first - mit1->first < pi; mit2++) {
      mit4 = M.upper_bound(mit2->first + pi);
      rv += (mit4->second - mit3->second); 
    }
  }

  /* Return the number of triangles divided by three, because we're counting
     each triangle three times. */

  return rv/3.0;
}