Cake

Interview

Time limit2sMemory limit1024 MB

Summary

Decide whether two perpendicular lines through the center can split the round cake into four pieces, each holding exactly one candle, with no line touching a candle.

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

Problem

Winnie-the-Pooh, Piglet, and Rabbit came to Christopher Robin's birthday party. The main gift is a huge round honey cake with four candles. Before anyone can eat it, the cake must be cut into four pieces. Knowing how much Winnie-the-Pooh loves honey, one could expect him to grab the biggest piece right away and get stuck in the doorway, as happened when he and Piglet visited Rabbit.

To avoid this, Christopher Robin decided to cut the cake into four equal parts. Since it is a festive cake and the cutting should stay simple, the cake must be cut with two perpendicular cuts through its center, so that each of the four pieces has exactly one candle. Also, no one should get half a candle and feel upset, so the cuts must not pass through any candle.

Input

The first line contains one integer $R$ $(1 \le R \le 10^9)$ , the radius of the cake. The center of the cake is the origin. The next four lines contain the coordinates of the candles $x_i, y_i$ . All candles are guaranteed to lie strictly inside the cake.

Output

Print <<YES>> if Christopher Robin can cut the cake as he wants, and <<NO>> if he cannot.

Examples1

Example 1
Input
```
10
0 1
1 0
0 -1
-1 0
```
Expected output
```
YES
```