CCC '06 S3 - Tin Can Telephone
View as PDFCanadian Computing Competition: 2006 Stage 1, Senior #3
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:
In these figures, "Romy" is Romy's window (the grid coordinates ) and "Jules" is Jules' window (grid coordinates
). 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 Specification
The input begins with a line containing four integer coordinates representing the locations of Romy's and Jules' windows. That is, the input ,
,
,
represents the coordinates
for Romy's window, and the coordinates
for Jules' window. You may assume that
.
The next line contains a single integer,
, identifying the number of buildings that will follow on the next
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
corners.
The sample input and output, shown below, corresponds to the first "blocked" situation described previously.
Output Specification
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 1Sample Output
1
Comments
That time you live in a triacontakaidigon shaped building.
I think morse-code is a good way for them :)
Is the view blocked if both people are inside a building?
Is Line2D disabled for this question? The code works in my IDE but returns Compilation error when submitting.
If they have web access, can't they just use email?
They could have just waited for the next day, so they can meet each other at school, but these girls have to be very impatient. I think they would go to the same school, there are diffrent factors: One, they are very good old friends. Two, most of the time schools (That are the same, like a school for sports is never near another school that is specificly for sports, but in total schools are just far away from each other). Also how can their parents take each other since they hate each other? I would have moved away.
Please don't judge me for my grammar
their parents took away their electronics bc they were playing too much minesweeper
This is 2008, they could've just used the house phone.
nah the parents will take away their computers too ;)