#3793. [Poi1999]祭坛问题

[Poi1999]祭坛问题

[POI1999]祭坛问题

题目背景

在中国民间,人们相信鬼只能沿直线移动。

在修建寺庙时,那是非常重要的。

题目描述

寺庙要修建在四边分别平行于南北西东的矩形位置之上。两个矩形不能有公共交点。

入口位于四堵墙中一堵的中间,门的宽度等于墙长度的一半。祭坛出现在寺庙的中间,矩形的对角线在那里相交。

鬼魂在这个点出现,那么寺庙被亵渎,当且仅当存在从祭坛射出的一束光线,通过入口到外面而且不与其他寺庙(位于建筑区域平行的地带)的墙壁相交或接触,这种情形才可能发生,也就是能在建筑区域从祭坛到无穷远处画一条直线而不碰到任何墙。

输入格式

第一行输入一个整数 nn

在接下来的 nn 行的每一行有一个寺庙的描述(在第 ii 行有第 i i 个寺庙的描述)。

寺庙的描述由四个非负的不大于 80008000 的整数和字母 E,W,SE,W,SN N 组成。头两个数字是寺庙的西北角的坐标,接下来的两个是相对的东南角的坐标。

描述的第五个元素代表入口的墙(E-东,W-西,S-南,N-北)。寺庙的描述元素由单空格隔开。

输出格式

接下来的几行,你的程序应该按升序写下可能被鬼魂亵渎的寺庙编号。每一个编号占一行。如果没有编号则输出 BRAK

样例 #1

样例输入 #1

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

1
2
5
6

提示

对于 100%100\% 的数据,1n10001 \le n \le 1000


样例解释: