SRM 641, D1, 250-Pointer (TrianglesContainOrigin)

James S. Plank

Wed Sep 4 13:40:55 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp when you copy it to TriangleseContainOrigin.
Problem Given in Topcoder: December, 2014
Competitors who opened the problem: 580
Competitors who submitted a solution: 285
Number of correct solutions: 216
Accuracy (percentage correct vs those who opened): 37.21%
Average Correct Time: ?

My writeup of this problem is in presentation form. You can find it here: http://web.eecs.utk.edu/~jplank/plank/classes/cs494/494/notes/TrianglesContainOrigin/.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given two vectors of integers, x and y.
They are the same size, containing values between -10,000 and 10,000.
Each (x[i], y[i]) defines a point on the cartesian coordinate system.
Each set of three points defines a triangle.
Your job is to count the number of triangles that contain the origin.
You are assured that the origin is either inside or outside of each triangle -- it will never be on an edge of the triangle.
x[i] and y[i] are between 3 and 2500 elements in size.

Examples

These are all included in main.cpp. If you give the input "-" to main.cpp, then it will read its values from standard input.

Example	x	y	Answer
0	`{-1,-1,1}`	`{1,-1,0}`	1
1	`{-1,-1,1,2}`	`{1,-1,2,-1}`	2
2	`{-1,-2,3,3,2,1}`	`{-2,-1,1,2,3,3}`	8
3	`{1,5,10,5,-5,7,-9,-6,-3,0,8,8,1,-4,7,-3,10,9,-6}`	`{5,-6,-3,4,-2,-8,-7,2,7,4,2,0,-4,-8,7,5,-5,-2,-9}`	256

The program genpoints.cpp will also generate random input for you, when you call a.out -.

Testing Yourself

Solution

I have three solutions:

Solution-Upper-Bound.cpp -- this uses upper_bound.
Solution-Faster.cpp -- this is the "faster" solution in the writeup that turns the O(n²log(n)) solution into O(n²).
Solution-Fastest.cpp -- this is the "fastest" solution that stops at 360 degrees so that you don't need to divide the final answer by three.

I also have:

time-it.sh       -- a shell script to time the three solutions
timing-graph.jgr -- jgraph of the timings
timing-graph.jpg -- jgraph of the timings, converted to JPG
timing-graph.pdf -- jgraph of the timings, converted to PDF
timings.txt      -- the output of time-it.sh