eolymp
bolt
Try our new interface for solving problems
Problems

Snooker

Snooker

Snooker is a game played on a billiard-table. The game was invented in the nineteenth century in India. The game is played with balls of equal radius, that we will consider equal to \textbf{1}. Snooker is played with the following set of balls: fifteen object balls that are not numbered and are solid red (called\textit{reds}), six object balls of other colors that are not numbered (called \textit{colors}) and a cue ball (called the \textit{white ball}). Due to the rules of the game the player make strikes until he makes a foul. His strikes in turn have object on red balls or on color balls. If the strike has object on red balls, the player must force the white ball to contact some red ball before any color one, if the player has object on color balls, he must force the white ball contact some color ball before any red one. If the player fails to do so, it is considered a foul (there are also other types of fouls which are of no interest to us in this problem). A special situation called snooker arises when there is no possibility to fulfil the requirement to hit the object ball with a direct strike. That means that if the center of the white ball moves along the straight line and the white ball does not make contact with borders of the table, it cannot hit any object ball without first hitting some forbidden one. Experienced snooker players can get out of snooker by making a strike with the help of the border or a spin strike, but snooker is indeed a big problem for beginners. Given positions of all balls on the table, you have to determine whether the position on the table is a snooker. For the purpose of this problem we will ignore the limitation that there can be at most fifteen reds and six colors and assume that there can be at most one hundred balls on the table. We will also ignore the size of the table and the existance of pockets, considering the game taking place on an infinite plane. \InputFile The first line of the input file contains \textbf{r} --- the number of reds, \textbf{c} --- the number of colors respectively, and the letter '\textbf{R}' if the object is on red balls and '\textbf{C}' if it is on color ones. Next line contains coordinates of the white ball. The following\textbf{r} lines contain coordinates of red balls, then \textbf{c} lines contain coordinates of color balls. All coordinates are real and do not exceed \textbf{1000.0} by their absolute value. No balls intersect, although some may touch each other. No ball touches the white ball. \OutputFile Output "\textbf{YES}" if the position on the table is a snooker and "\textbf{NO}" if it is not.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4 2 C
0.0 0.0
1.8 1.8
1.8 -1.8
-1.8 1.8
-1.8 -1.8
3.0 4.0
-6.0 -2.0
Output example #1
YES
Source Russian Teams Training Sessions in Petrozavodsk, Summer 2004, Andrew Stankevich Contest 8, Thursday, August 26, 2004