FLAGSProblem code: INS0905 |
A new format of a robotic competition requires a participant to make a robot that touches flags to score points. Initially, the robot can be set at any of the flags, facing any direction, with 2 parameters set: the distance it moves and a direction, left or right. The robot then moves that distance, turns 90 degrees in the direction set, then moves that distance again, turns again, and so on, alternating between move and turn until it reaches it's original flag. If the robot touches a flag at each location where it turns, the robot scores a point. The robot may then be set at any flag, and the process repeated. The robot cannot go through the same sequence of flags to score multiple points.
Input
The first line gives t, the number of test cases( t 300 ). Then t test cases follow.
For each test case:
The first line gives n, the number of flags,
The next n lines give 2 integers x y each, for the x and y coordinate of each flag.
(0 < n 2000)
(-30000 < x < 30000)
(-30000 < y < 30000)
Output
For each test case output a single line.
print number x, denoting the maximum number of points a robot can score given a set of flags.
Example
Input: 2 6 0 0 0 1 0 2 1 0 1 1 1 2 7 0 1 9 9 3 6 2 1 1 2 5 7 1 0 Output: 16 8
| Author: | fctrl |
| Date Added: | 14-10-2009 |
| Time Limit: | 10 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, C, C99 strict, CAML, CLPS, CPP 4.0.0-8, CS2, D, ERL, FORT, HASK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
the time limt for this
the time limt for this problem is 10 s.
Can you clarify how the
Can you clarify how the output of the second test case is 8. (Can you give the sequence of moves)?
Constraints
Constraints corrected:
0<t<=20
0<n<=6000
0<=x<=800
0<=y<=800
@Venkatesh: the number of
@Venkatesh: the number of points it scores for the given 7 flags is correct. Each of the eight sequences are different.