← 返回题目列表

AtCoder · utpc2012_04

D. 两张地图

中文机器翻译题面 查看原题

問題

将两幅不同比例的日本地图叠加时,总会出现相同地点重合的点。

准备地图 A 及缩小后的地图 A',将 A' 放置使其不超出 A 的范围。这样,就存在且仅存在一个点 p 在 A 上,与 A' 上对应的点 p' 位于同一位置!

凸多边形地图 A,以及将其缩小一半、旋转并平移后恰好落入原地图内的地图 A',以二维空间的坐标给出。求出在地图 A 和 A' 中都表示相同地点(上面的 p 和 p')的点的坐标。


在右边的状态下给出两张地图。红点为所求的点。

入力

n
x_{11} y_{11}
...
x_{1n} y_{1n}
x_{21} y_{21}
...
x_{2n} y_{2n}

第一行为多边形的顶点数量。 n 。 继续 关键信息在 n 接下来的行给出大边形的顶点坐标,按逆时针顺序。 n 接下来的行给出缩小后的多边形顶点坐标,按逆时针顺序。 (x_{1k}, y_{1k}) 与 (x_{2k}, y_{2k}) 相对应。

出力

将所求点的坐标按 x, y 的顺序以空格分隔输出在一行上,允许绝对误差 10^{-6} 。

制約

  • 可以假设地图是无自交的凸单多边形。
  • 约化多边形的所有坐标都在原多边形内部。
  • 收缩总是一半
  • 3 \leq n \leq 20.
  • 0 \leq x_{1k}, y_{1k}, x_{2k}, y_{2k} \leq 100.
  • 可以接受假设多边形在约简前的所有边至少为1。
  • 约简多边形的坐标为实际坐标,截断九个小数位。

部分点

针对这个问题,设置了一组50个测试用例。 包含在该组中的测试用例输入必须满足以下条件。

  • n = 4
  • (x_{11},y_{11}) = (0,0)
  • (x_{12},y_{12}) = (100,0)
  • (x_{13},y_{13}) = (100,100)
  • (x_{14},y_{14}) = (0,100)
  • (x_{22},y_{22}) = (x_{21}+50,y_{21})
  • (x_{23},y_{23}) = (x_{21}+50,y_{21}+50)
  • (x_{24},y_{24}) = (x_{21},y_{21}+50)

入力例 1

4
0 0
100 0
100 100
0 100
25 25
75 25
75 75
25 75

输入示例 1 的输出示例

50.000000000 50.000000000

输入多边形图。红点 (x_{11}, y_{11}) 蓝点 (x_{21}, y_{21}) 。

入力例 2

4
0 0
100 0
100 100
0 100
0.5 1.5
50.5 1.5
50.5 51.5
0.5 51.5

输入示例 2 的输出示例

1.000000000 3.000000000

入力例 3

8
2.0 1.0
3.0 1.0
4.0 2.0
4.0 3.0
3.0 4.0
2.0 4.0
1.0 3.0
1.0 2.0
2.9 1.3
3.3 1.6
3.4 2.3
3.1 2.7
2.4 2.8
2.0 2.5
1.9 1.8
2.2 1.4

输入示例 3 的输出示例 一直到

3.0 2.0