/* Topcoder SRM 641, D1, 250-Pointer (TrianglesContainOrigin) James S. Plank Tue Sep 5 12:05:39 EDT 2017 */ #include #include #include #include #include #include using namespace std; class TrianglesContainOrigin { public: long long count(vector x, vector y); }; long long TrianglesContainOrigin::count(vector x, vector y) { int i; map 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 ::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. */ 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; }