Candles

Interview

Time limit2sMemory limit1024 MB

Summary

Given n candle points inside a circle and m lines that cut the cake, decide whether some region bounded by the lines contains two or more candles.

Level: Medium5 of 10
Topics: Geometry, Hash map, Sorting, Implementation
Solved: No attempts yet

Problem

Misha has turned $n$ years old. The birthday cake baked for the occasion is a circle of radius $r$ centered at the origin. There are $n$ candles on the cake. Misha's mother divided the cake into pieces by making $m$ straight cuts. Each guest took one of the resulting pieces.

Misha wants to know whether any of his guests ended up with more than one candle. Help him find out.

Input

The first line of the input file contains the integers $n$ , $m$ , and $r$ ( $1\le n\le 10000$ , $0\le m\le 1000$ , $1\le r\le 2000$ ).

The following $n$ lines contain pairs of integers $x\_i, y\_i$ , the coordinates of the points where the candles are placed. These points lie inside the circle, and the size of the candles can be ignored. No two candles coincide.

The last $m$ lines describe the cuts, each with three integers $a\_i, b\_i, c\_i$ . Such a triple corresponds to the cut given by the equation $a\_i x + b\_i y + c\_i = 0$ . No cut passes through a candle. No two cuts coincide. The values of $a\_i, b\_i, c\_i$ do not exceed $10000$ in absolute value.

Output

If one of the guests got more than one candle, output the word <<YES>> to the output file, otherwise output the word <<NO>>.

Examples3

Example 1
Input
```
3 2 3
2 2
1 -1
-2 0
2 -1 0
0 1 -1
```
Expected output
```
NO
```
Example 2
Input
```
3 2 3
2 2
1 -1
-2 0
1 1 -1
0 1 -1
```
Expected output
```
YES
```
Example 3
Input
```
1 0 100
0 0
```
Expected output
```
NO
```