CCC '06 S3 - Tin Can Telephone - Olympiads Online Judge

CCC '06 S3 - Tin Can Telephone

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian 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:

$\text{[math]}$

In these figures, "Romy" is Romy's window (the grid coordinates $0,0$ $0, 0$ ) and "Jules" is Jules' window (grid coordinates $3,3$ $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 Specification

The input begins with a line containing four integer coordinates representing the locations of Romy's and Jules' windows. That is, the input $x_R$ $x_{R}$ , $y_R$ $y_{R}$ , $x_J$ $x_{J}$ , $y_J$ $y_{J}$ represents the coordinates $(x_R, y_R)$ $(x_{R}, y_{R})$ for Romy's window, and the coordinates $(x_J, y_J)$ $(x_{J}, y_{J})$ for Jules' window. You may assume that $-1000 \le x_R, x_J, y_R, y_J \le 1000$ $- 1000 \leq x_{R}, x_{J}, y_{R}, y_{J} \leq 1000$ .

The next line contains a single integer, $n$ $n$ $(0 \le n \le 100)$ $(0 \leq n \leq 100)$ , identifying the number of buildings that will follow on the next $n$ $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$ $32$ 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

Copy

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

Sample Output

Copy

Comments

3

Viv_CCGS commented on March 19, 2024, 9:43 a.m. ← edited →

That time you live in a triacontakaidigon shaped building.

0

Tommy_Shan commented on July 30, 2021, 8:38 p.m.

I think morse-code is a good way for them :)

1

Evanhyd commented on Feb. 8, 2021, 11:05 p.m. ← edit 3 →

Is the view blocked if both people are inside a building?

5

4fecta commented on June 19, 2019, 1:58 a.m.

Is Line2D disabled for this question? The code works in my IDE but returns Compilation error when submitting.

45

AliSatec commented on Feb. 8, 2017, 11:21 p.m.

If they have web access, can't they just use email?

-6

Haoyun commented on June 7, 2022, 3:05 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

9

AlanCCCL2S18 commented on Feb. 7, 2020, 12:01 a.m.

their parents took away their electronics bc they were playing too much minesweeper

6

JJ_G4M3R commented on Dec. 17, 2018, 1:25 a.m.

This is 2008, they could've just used the house phone.

9

ThatGuyOnTheStreet commented on Dec. 2, 2018, 9:19 p.m.

nah the parents will take away their computers too ;)