Machine Learning

Pop-Quiz for the Club

Your club is running a quick badge-guessing game. Everyone stands on a 2D map with their badge shown as either star or circle. To check how well the group can guess badges without peeking, each member is “held out” in turn and guessed from the closest other member using Manhattan distance (L1). Count how many of these guesses are correct.

The first line of the input contains a single integer n representing the number of club members.

The next n lines contain two floating-point numbers x y followed by a badge word, describing one member’s position and badge.

The program should print a single integer - the number of correct leave-one-out guesses.

Input

Output

4
0 0 star
1 0 star
2 0 circle
3 0 circle

3

5
0 0 star
0 1.5 star
0 2.5 circle
2.2 0 circle
2.2 1.0 circle

3

4
0.0 0.0 circle
1.2 0.0 circle
0.0 1.2 star
3.4 0.0 star

2

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue