#P16869. [Ural1662]Goat in the Garden 6

    ID: 16079 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-有限候选集缩减暴力枚举直线与圆相交圆相交点到线段距离点在多边形内

[Ural1662]Goat in the Garden 6

题目描述

菜地是一个凸多边形。Ivan 要在地面上打下一根木桩,并把两只羊拴在木桩上:

  • 大山羊的绳长为 RR,要求它能够到达菜地中的任意一点;
  • 小羊的绳长为 rr,要求它无法到达菜地的任意内部点。

已知 1≤r<R1\le r<R。请找出一个满足要求的木桩位置。

忽略木桩和两只羊本身的大小。

输入格式

第一行一个整数 NN:

3≤N≤50.3\le N\le 50.

接下来 NN 行,每行两个整数 Xi,YiX_i,Y_i,表示凸多边形顶点,按边界顺序给出。

∣Xi∣,∣Yi∣≤1000.|X_i|,|Y_i|\le 1000.

最后一行两个整数 r,Rr,R:

1≤r<R≤1000.1\le r<R\le1000.

输出格式

如果存在合法位置,输出两个实数 x,yx,y,表示木桩坐标。坐标应精确到 10−610^{-6}。

如果不存在合法位置,输出:

No solution

样例 1

4
0 0
0 1
1 1
1 0
1 3
0.500000 -1.000000

样例 2

3
0 0
0 14
2 7
8 10
No solution