SRM 734, D2, 250-Pointer (TheRoundCityDiv2)

James S. Plank

Wed Aug 22 00:55:19 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: May, 2018
Competitors who opened the problem: 93
Competitors who submitted a solution: 86
Number of correct solutions: 83
Accuracy (percentage correct vs those who opened): 89.2%
Average Correct Time: 12:39

Perhaps this makes me a bad computer scientist, but when I see one of these D2 250 problems, I often look at the constraints and ask myself whether a truly boneheaded solution will be fast enough. In the case of this problem, I saw that r's maximum value was 100, so a brain-dead enumeration of all potential (x,y) points would consider 201*201 = 40401 points. That's a small number, topcoder-wise, so I didn't do anything fancy:

Enumerate all possible values of x.
Enumerate all possible values of y.
If (x,y) is in the circle and is not (0,0), then increment the answer.

For this one, you don't need to use the sqrt() function, because you can simply take the square of the distance formula: (x,y) is in the circle if x² + y² ≤ r².

Obviously, you can solve this differently and much faster, but with the constraints as they are, you don't need to think too much about it. I would predict that the non-working solutions were people who used math and got some detail incorrect.