2006 Canadian Computing Competition, Stage 1

Problem S3: Tin Can Telephone

Romy and Jules have been talking with each other on their cell phones. Unfortunately, their parents dislike each other and have decided that they can no longer call each other. In fact, their parents have taken their cell phones away. So, Romy and Jules must find some other way to communicate.

After searching the web for ideas, they have decided to build a “tin can” telephone.

Simply, a tin can telephone is two empty soup cans attached to each other with a string. To use it, the string must be stretched tight and then one person speaks while the other person listens. It is important that nothing touches the string so that it can vibrate and transfer sound from one can to the other.

To successfully set up a tin can telephone, Romy and Jules are going to need a clear line of sight between their two bedroom windows. To determine if they can run the string between their rooms, they get out a map that uses simple integer coordinates. Now consider the following three situations:

1. Blocked View 2. Clear View 3. Blocked View (Touching)

In these figures, “Romy” is Romy’s window (the grid coordinates 0,0) and “Jules” is Jules’ window (grid coordinates 3,3). In the first figure, there is a building between their windows, and it blocks the line of sight between them. In the second figure, the building doesn’t block their view and they can successfully set up a tin can phone. In the third figure, a line drawn from Romy’s coordinates to Jules’ coordinates would touch the corner of the building. Since the string cannot touch anything, they cannot set up a tin can telephone and the view is considered as blocked.

Input

The input begins with a line containing four integer coordinates representing the locations of Romy’s and Jules’ windows. That is, the input xR, yR, xJ, yJ represents the coordinates (xR, yR) for Romy’s window, and the coordinates (xJ, yJ) for Jules’ window. You may assume that -1000 ≤ xR, xJ, yR, yJ ≤ 1000.

The next line contains a single integer, n (0 ≤ n ≤ 100), identifying the number of buildings that will follow on the next n lines. Each building is on a separate line and begins with an integer specifying the number of corners that the building has. This integer is followed by the integer coordinates of the building’s corners, in either clockwise or counter-clockwise order. No building has more than 32 corners.

The sample input and output, shown below, corresponds to the first “blocked” situation described previously.

Output

For the input data, output a single number identifying the number of buildings that touch or block the line of sight.

Sample Input

0 0 3 3
1
4 1 2 2 2 2 1 1 1

Sample Output

1

All Submissions
Best Solutions


Point Value: 12
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 04, 2008

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

seems kind of hard, with objects having up to 32 vertices

Hint: The actual shapes of the polygons are irrelevant. (You're overthinking it - it really is worth only 5 points.)

can the coordinates for Jules or Romy be inside one of the buildings?

No (I'm not 100% sure, but my code works without checking that)