Homer's problem P92553


pdf   zip


Homer Simpson is a good customer of Moe’s bar. However, due to the crisis, some other bars (mostly the ones in Shelby ville, but also the new ones opened by Apu and Barney) have lowered their prices, so Homer might now be in other bars drinking beer. Marge, of course, is not happy with this situation. Help her to find in which bars Homer might be.

We are before episode S03E04, in which Professor Frink invents the “Frinkahedron” (cube). Therefore, we only have 2D-grid information about the space in which Homer is. You will be given the coordinates of each of the bars, and you must print in which of them (0-based) Homer might be. Note that bars might be constructed on top of each other, so Homer might be at two or more different bars.

Marge is also tracking how many friends are drinking with Homer. So, in case that Homer might be in a bar, you also have to compute how many friends could be in that bar with him. Marge knows that bars are full, and that the chairs of bars are located at every point with integer coordinates, the points on the boundary inclusive.


Input begins with the number of cases. Every case begins with the number of bars (each one a convex polygon). For every bar, you are given the number of vertices (between 3 and 1000), followed by the coordinates of the vertices in clockwise or counterclockwise order. After all the bars have been described, the position of Homer is given. All coordinates are integer and have absolute value at most 105.


For every case, print in order the bars in which Homer could be, together with the number of other customers in every bar. If there are no such bars, print “He is at home.” in one line. Print a blank line between the output for two cases.

Public test cases
  • Input

    4   0 0  4 0  4 3  0 3
    2 1
    100000 -100000
    3   0 2  4 0  0 0
    5   1 0  2 -1  2 -3  0 -3  0 -1
    4   1 -1  3 -1  3 1  1 1
    2 0
    3   -2 -4  0 0  4 -4
    3 -1
    4   -100000 -100000  -100000 100000  100000 100000  100000 -100000
    0 0


    He may be at bar number 0, with another 19 customers.
    He is at home.
    He may be at bar number 0, with another 8 customers.
    He may be at bar number 2, with another 8 customers.
    He is at home.
    He may be at bar number 0, with another 40000400000 customers.
  • Information
    Javier Gómez
    Official solutions
    User solutions