Polish version    English version  
  History of OI -> VI OI 1998/1999 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
VI Olimpiada Informatyczna 1998/1999

Task: OLT
Author:
Altars

III stage contest  

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. 

Task

Write a program which: 

  • reads descriptions of the temples from the input file OLT.IN,
  • verifies which temples could be profaned,
  • writes their numbers in the text file OLT.OUT.

Input

In the first line of the text file OLT.IN 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.

Output

In the following lines of the text file OLT.IN 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 file OLT.OUT you should write one word: BRAK ( means "lack" in Polish). 

Example

For the input file OLT.IN:

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
the correct answer is the output file OLT.OUT
1
2
5
6
The picture shows the temples described in the file OLT.IN. The dashed lines show possible routes of evil spirits.



Print friendly version