13084 - Cameras as Invigilators

dibery · Post by **dibery** » Wed Apr 20, 2016 5:06 am

Getting several WA for this problem.
I've tried many solutions but none worked.

Here's my solution: (spoiler below)

1. Generate all lines that can be drawn in 5001x5001 grid. (As the longest line is 5000x5000, I didn't generate lines longer than 5000.)
2. For each possible line (sorted in order), check lines forward. If these 2 lines are trouble with each other, mark all points on both lines as troubled.
3. Check 2D array to see which points are troubled. As the cameras are symmetric, I check from one side and take the symmetry of it.

Code: Select all

Code removed after AC.

Also some IO:
Input

Code: Select all

Output:

Code: Select all

Is my output correct?
Any help would be appreciated.

EDIT: This cases above is checked after getting AC, so I left them here for people who might need.

One more case, "5000 25000000" has 65631 troubled points.