CCC '06 S3 - Tin Can Telephone

View as PDF
Submit solution
Points: 12
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:

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 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, y_R, x_J, y_J represents the coordinates (x_R, y_R) for Romy's window, and the coordinates (x_J, y_J) for Jules' window. You may assume that -1000 \le x_R, x_J, y_R, y_J \le 1000.

The next line contains a single integer, n (0 \le n \le 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 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 1

Sample Output

1

Comments


  • 1
    Viv_CCGS  commented on March 19, 2024, 9:43 a.m.

    That time you live in a triacontakaidigon shaped building.


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

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


  • 0
    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.


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

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


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

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


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

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


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

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


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

      nah the parents will take away their computers too ;)