CF799G Cut the pie

题目描述

有一个 $n$ 边形,保证是一个凸包,其中 $n$ 个顶点的坐标都已经给出。有 $q$ 次询问,每次询问都给出一个点的坐标,你需要过这个定点把这个$n$边形切成面积相等的两部分,我们称这条线为等分线。对于每次询问,输出一个数,为等分线由 $x$ 坐标轴逆时针转动的角度,用弧度制输出。比如说,等分线为 $y$ 轴,那么你应该输出 $1.5707963267948966192313216916398$,因为 $y$ 轴是由 $x$ 轴逆时针转动 $90^{\circ}$ 而得,化为弧度制即为 $\frac{\pi}{2}$。

输入格式

第一行两个整数 $n$ 和 $q$。 接下来 $n$ 行,一行输入 $2$ 个数,为这个 $n$ 边形 $n$ 个点的坐标,点由顺时针方向给出。保证了多边形的严格凸性,特别是没有三个顶点在同一条直线上。 再接下来 $q$ 行,一行输入 $2$ 个数,为每次询问的定点的坐标。

输出格式

一共 $q$ 行,每行为每次询问的结果。如果过这个点无法将这个 $n$ 边形切成面积相同的两块,输出 $-1$。 ### 数据测试点范围: $3\le n\le 10^4$,$1\le q\le 10^5$,所有点的坐标(包括 $n$ 边形的顶点坐标以及每次询问的定点坐标)都满足:$-10^6\le x,y\le 10^6$。