Cut the pie

题意翻译

有一个$n$边形，其中$n$个顶点的坐标都已经给出。有$q$次询问，每次询问都给出一个点的坐标，你需要过这个定点把这个$n$边形切成面积相等的两部分，我们称这条线为等分线。对于每次询问，输出一个数，为等分线由$x$坐标轴逆时针转动的角度，用弧度制输出。比如说，等分线为$y$轴，那么你应该输出$1.5707963267948966192313216916398$，因为$y$轴是由$x$轴逆时针转动$90$°而得，化为弧度制即为$π/2$。 ### 输入格式： 第一行两个整数$n$和$q$； 接下来$n$行，一行输入$2$个数，为这个$n$边形$n$个点的坐标； 再接下来$q$行，一行输入$2$个数，为每次询问的定点的坐标。 ### 输出格式： 一共$q$行，每行为每次询问的结果。如果过这个点无法将这个$n$边形切成面积相同的两块，输出$-1$。 ### 数据测试点范围： $3$<=$n$<=$10^4$，$1$<=$q$<=$10^5$，所有点的坐标（包括$n$边形的顶点坐标以及每次询问的定点坐标）都满足：$-10^6$<=$x,y$<=$10^6$

题目描述

Arkady reached the $ n $ -th level in Township game, so Masha decided to bake a pie for him! Of course, the pie has a shape of convex $ n $ -gon, i.e. a polygon with $ n $ vertices. Arkady decided to cut the pie in two equal in area parts by cutting it by a straight line, so that he can eat one of them and give the other to Masha. There is a difficulty because Arkady has already put a knife at some point of the pie, so he now has to cut the pie by a straight line passing trough this point. Help Arkady: find a line that passes through the point Arkady has put a knife into and cuts the pie into two parts of equal area, or determine that it's impossible. Your program has to quickly answer many queries with the same pie, but different points in which Arkady puts a knife.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 3<=n<=10^{4} $ , $ 1<=q<=10^{5} $ ) — the number of vertices in the pie and the number of queries. $ n $ line follow describing the polygon vertices in clockwise order. The $ i $ -th of these line contains two integers $ x_{i} $ and $ y_{i} $ ( $ -10^{6}<=x_{i},y_{i}<=10^{6} $ ) — the coordinates of the $ i $ -th vertex. It is guaranteed that the polygon is strictly convex, in particular, no three vertices line on the same line. An empty line follows. $ q $ lines follow describing the query points. The $ i $ -th of these lines contain two integers $ x_{i} $ and $ y_{i} $ ( $ -10^{6}<=x_{i},y_{i}<=10^{6} $ ) — the coordinates of the point in which Arkady puts the knife in the $ i $ -th query. In is guaranteed that in each query the given point is strictly inside the polygon, in particular, is not on its edges.

输出格式

For each query print single integer — the polar angle of the line that is the answer for the corresponding query, in radians. The angle should be in the segment $ [0;π] $ , the angles are measured from the direction of $ OX $ axis in counter-clockwise order. For example, the polar angle of the $ OY $ axis is . If there is no answer in that query, print -1. If there are several answers, print any of them. Your answer is considered correct if the difference between the areas of the parts divided by the total area of the polygon doesn't exceed $ 10^{-4} $ by absolute value. In other words, if $ a $ and $ b $ are the areas of the parts after the cut, then your answer is correct if and only of .

输入输出样例

输入样例 #1

3 1
0 0
0 3
3 0

1 1

输出样例 #1

2.67794504460098710000

输入样例 #2

5 3
6 5
6 3
5 0
0 0
0 5

5 4
3 3
5 2

输出样例 #2

0.60228734612690049000
1.27933953226473580000
2.85805511179015910000