Problem K
Knox

Alarm system

Ellen has just bought herself a new fort to protect all her precious belongings. Her fort is of course very well protected, and in fact the only possible point of entry is the main hallway. Ellen’s hallway is a big room with a long and narrow path through the center (aligned with the x-axis). The narrow path is the only place possible to walk, as both sides of the path are guarded by an electric fence. However, Ellen feels that this is not enough, and wants to invest in a motion detection alarm system to protect the hallway.

The alarm system she wants to buy consists of laser emitters and reflectors that can be paired together. The emitters send out a laser in a sector with a width of $a$ degrees and a unique frequency $f_ i$. If a reflector is placed inside this sector, set to the correct frequency and turned exactly towards the emitter, the laser will be reflected back to the emitter, and a barrier is formed. The emitters, reflectors and brackets are all made of a special transparent material such that the lasers pass straight through them, with the only exception being laser and the reflector tuned to the same frequency.

Fortunately, the previous owner had already bought such an alarm system, but he took the emitters with him when he left. Hence, the reflectors and brackets for the emitters are still standing. All the brackets for the emitters are placed on one side of the room, such that the center line of the sector is normal to the x-axis. Ellen’s task is to buy new emitters, turn the reflectors to face each of the emitters and set them to the corresponding frequency.

In the hasty bidding process for her new fort, Ellen spent a bit more money than she would have liked. Now she would want to reuse the alarm setup that already exists, and spend as little money as possible on her new laser emitters. The price of the emitters is directly proportional to the width of the laser sector, and the manufacturer also adds a huge fee for ordering emitters with different widths. So given that all the emitters have the same sector width, what is the smallest sector width $a$ she can order for the emitters and still be able to connect all the emitters to a reflector?

Input

On the first line, you are given one positive integer, $N$ denoting the number of emitters and reflectors.

Then follow $N$ lines, each with two space-separated numbers, $x_ i$ and $y_ i$, representing the coordinate of the i’th laser emitter bracket.

Then follow $N$ more lines, each with two space-separated numbers, $x_ j$ and $y_ j$, representing the coordinate of the j’th reflector.

Output

One number, $a$, the minimal sector width (in degrees) necessary to connect each reflector to exactly one emitter. Your answer must have an absolute or relative error of at most $10^{-6}$.

Limits

• $0 < N \leq 300$

• $-1\, 000 \leq x_{i}, x_{j} \leq 1\, 000$

• $-1\, 000 \leq y_{i} < 0$

• $0 < y_{j} \leq 1\, 000$

• All real numbers in the input have at most $4$ digits after the decimal point.

Sample Explanation

Sample Input 1 is shown in the figure at the top of the problem.

2
4.0 -3.0
10.0 -3.0
9.0 2.0
2.0 2.0

43.6028189727036