0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
According to Chinese folk believes evil spirits can move only on a straight line. It is of a great importance when temples are built. The temples are constructed on rectangular planes with sides parallel to the north - south or east - west directions. No two of the rectangles have common points. An entrance is situated in the middle of one of four walls and its width is equal to the half of the length of the wall. An altar appears in the center of the temple, where diagonals of the rectangle intersect. If an evil spirit appears in this point, a temple will be profaned. It may happen only if there exists a ray which runs from an altar, through an entrance to infinity and neither intersects nor touches walls of any temple (on a plane parallel to the plane of a construction area), i.e. one can draw at a construction area a line which starts at the altar and runs to the infinity without touching any wall.
Write a program which:
1.reads descriptions of the temples,
2.verifies which temples could be profaned,
3.writes their numbers.
In the first line of the input one integer n, the number of temples 1 <= n <= 1000, is written.
In each of the following n lines there is a description of one temple (in i-th line a description of the i-th temple). The description of a temple consists of four non-negative integers, not greater than 8000 and a letter E, W, S or N. Two first numbers are coordinates of a temple’s northern-west corner and two following are coordinates of an opposite southern-east corner. In order to specify coordinates of a point first we give its geographical longitude, which increases from the west to the east, and then its latitude, which increases from the south to the north. The fifth element of the description indicates the wall with the entrance (E — eastern, W —western, S — southern, N — northern). The elements of the temple’s description are separated by single spaces.
In the following lines of the output your program should write in ascending order numbers of the temples, which may be profaned by an evil spirit. Each number is placed in a separate line. If there are no such numbers, in the output you should write one word: BRAK ( means “lack” in Polish).
6 1 7 4 1 E 3 9 11 8 S 6 7 10 4 N 8 3 10 1 N 11 4 13 1 E 14 8 20 7 W
1 2 5 6 hint: The picture shows the temples described in the file OLT.IN. The dashed lines show possible routes of evil spirits.
0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。