Poi2013 Tapestries

题目描述

An exhibition of tapestries is opening in Byteotian Museum of Fine Arts. The main exhibition room, viewed from top, is a polygon (not necessarily convex). A tapestry is hanged on each wall of the room, each tapestry taking all the area of its wall.
A lamp has been installed in the room in order to illuminate the exhibition. The lamp is glowing uniformly in all directions. However, while some of the tapestries have to be flooded with light, others cannot be exposed to strong light.
Byteasar, the curator, has been moving the lamp around the room, but so far he is not satisfied with the results. Now he is terrified by the prospect of moving the tapestries around instead - this would require much effort, and the exhibition is to open soon. Perhaps you will be able to tell him if his attempts are doomed or not?
Your task is to determine if there is such a spot that placing the lamp in it satisfies the following:
• each wall is to be either completely illuminated or completely shaded, as required by the tapestry hanging on it; there can be no wall that is partly illuminated and partly shaded;
• if the lamp is located exactly on the wall or its extension, this wall is not illuminated;
• the lamp can neither be switched off nor taken away from the room; it has to be on while located (strictly) inside the room (i.e., it cannot be placed in a corner or on any wall).

给定一个不自交、无重点、无三点共线的多边形，多边形每条边都被要求必须有灯光直射或者必须没有，只有一部分照射或者没有照射到都是不合法的。求问是否存在一个点能够满足这个条件。

---

输入格式

There is a single integer t (1<=t<=20) in the first line of the standard input, denoting the number of data sets. The following lines describe these data sets.
The first line of a single description holds a single integer N （3<=N<=1000）, denoting the number of walls in the main exhibition room. Then the following N lines specify the room's shape. Each of those lines contains a pair of integers Xi and Yi (-30000<=Xi,Yi<=30000) for i=1,2…N, separated by a single space, denoting the coordinates of the room's corner or, in other words, the vertex of corresponding polygon. The vertices are given clockwise.
The next n lines specify the tapestries' requirements. Each of those lines contains a single letter, S or C, denoting that the wall has to be illuminated or shaded, respectively. The letter in the i-th of these lines （for 1<=i<=N-1） regards the wall between the  -th and the (i+1)-th vertex. The letter in the last of these lines regards the wall between the last and the first vertex.
The polygon depicting the room's shape has no self-crossings, i.e., with the exception of successive sides, which share a common vertex, no two sides of the polygon share a common point. Furthermore, no three vertices of the polygon are collinear.

第一行一个t代表数据组数

每组数据第一行一个n代表多边形点数

接下来n行每行一个数代表第i个点的坐标，点按顺时针顺序给出。

最后n行每行一个S（代表需要照射）或者C（代表不需要照射）。前n-1行第i行的边是第i个给定的点和第i+1个给定的点的边，最后一行的边是第1和n个点之间的边。

---

输出格式

For each data set your program should print to the standard output a single line containing a single word:
• TAK (Polish for yes) if the lamp can be placed so as to satisfy all aforementioned requirements, or
• NIE (Polish for no) otherwise.
Example
In the figures below the examples, the thick sides denote the walls that have to be shaded while the remaining sides - the walls that have to be illuminated. The figure for the first example shows a correct placement of the lamp.

每行一个TAK（代表存在）或NIE（代表不存在）

---

样例输入

1
16
5 -3
4 -4
3 -7
0 -5
-3 -7
-4 -4
-5 -3
-1 -1
-4 3
-2 4
-1 2
0 7
1 2
2 4
4 3
1 -1
C
S
S
S
S
C
C
S
S
C
S
S
C
S
S
C
        
 

---

样例输出

TAK

---

提示

---

题目来源

鸣谢HJWJBSR提供译文