#P18081. Night at the Museum

Night at the Museum

Night at the Museum

一名守卫按顺序沿闭合折线巡逻。路线顶点依次为 P1,P2,…,PnP_1,P_2,\ldots,P_n:先从 P1P_1 走到 P2P_2,依次走到 PnP_n,最后从 PnP_n 回到 P1P_1。

守卫在每一段路线上都面朝当前移动方向。其视野是以当前位置为圆心、半径为 rr、中心方向为前进方向、左右各张开 aa 度的扇形,即整个扇形的圆心角为 2a2a 度。

平面上有 mm 件展品。展品位于该扇形内或边界上时可见。对每个 k=0,1,…,mk=0,1,\ldots,m,求巡逻过程中恰好能看见 kk 件展品的路段总长度。

重复经过的路线按每次经过分别累计;统计的是沿路线行走的长度。折线转折点本身长度为零,不影响答案。

输入格式

本题只有一组数据。

第一行四个整数 n,m,r,an,m,r,a。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,为路线顶点坐标。

再接下来 mm 行,每行两个整数 xi′,yi′x'_i,y'_i,为展品坐标。

输出格式

输出 m+1m+1 行。第 k+1k+1 行输出恰好看见 kk 件展品的路线总长度。

设你的输出为 xx,标准答案为 yy,每个数均须满足

∣x−y∣max⁡(1,∣y∣)≤10−6.\frac{|x-y|}{\max(1,|y|)}\le10^{-6}.

数据范围

  • 3≤n≤20003\le n\le2000,1≤m≤20001\le m\le2000;
  • 1≤r≤1041\le r\le10^4,1≤a≤891\le a\le89,aa 为整数度数;
  • 所有坐标均为 [−104,104][-10^4,10^4] 内的整数;
  • 相邻路线顶点不同,且 Pn≠P1P_n\ne P_1;
  • 非相邻顶点可以相同,路线可以自交,展品坐标可以重复。位置相同的多件展品分别计数。

样例 1

输入:

3 2 3 45
1 1
5 5
8 1
2 3
4 2

输出:

14.178145584873
2.247170915928
1.231537748691

样例 2

输入:

4 1 3 60
0 0
6 6
6 0
0 6
2 1

输出:

25.279547784093
3.691014964384