1262: SimplePhysics
题目
题目描述
《简单物理学/SimplePhysics》是一款物理/力学为基础的游戏，可惜这款游戏已经停更多年。作者也早已开发出《SimpleRockets》以及《SimplePlanes》等高度物理仿真的游戏续作。特别是在《简单火箭》的游戏中，不会造轮船的汽车设计师不是好的飞行员……
在一张无限大木桌上，有 $N$ 个钉子一根绳子，绳子的两端从桌上的两个孔洞中穿了过去。现在，从桌下拉紧绳子的两端，绳子会慢慢收紧，直到所有地方都绷紧不能移动。你的任务是求出最终留在桌面上的绳长。
我们将会用多条线段来描述这根绳子的初始状态，并且保证初始状态的绳子不会接触到任何一个钉子。
你可以参考以下的三个例子来了解这一个拉伸的过程：
- 图1
- 图2
- 图3
输入格式
第一行是两个整数 $M, N$，分别表示刚开始绳子的节点数以及钉子的个数
接下来的 $M$ 行，每行两个整数 $x, y$ 表示绳子初始状态的一个节点。第 $1$ 个节点和第 $M$ 个节点代表了木桌上的孔洞。这根绳子的初始状态就是由 $1\sim M$ 这些节点顺次连接得到的
接下来的 $N$ 行，每两两个整数 $x,y$ 表示木桌上的 $N$ 个钉子
输出格式
输出一个小数，表示绳子最终留在桌面上的长度
本题有 spj，你的答案和正确答案的差距不超过 0.001 就会被认为正确
样例输入
样例输入 1
text
6 16
5 4
11 988
474 975
459 16
985 12
984 982
242 227
140 266
45 410
92 570
237 644
370 567
406 424
336 290
756 220
634 251
511 404
575 554
726 643
868 571
907 403
845 283
样例输入 2
text
10 4
261 196
943 289
859 925
56 822
112 383
514 0
1000 457
514 1000
0 485
233 224
710 242
850 654
485 915
140 663
样例输入 3
text
26 5
0 953
180 0
299 501
37 301
325 124
162 507
84 140
913 409
635 157
645 555
894 229
598 223
783 514
765 137
599 445
695 126
859 462
599 312
838 167
708 563
565 258
945 283
251 454
125 111
28 469
1000 1000
185 319
717 296
9 315
372 249
203 528
样例输入 4
text
15 15
200 247
859 597
340 134
967 247
421 623
1000 427
751 1000
102 737
448 0
978 510
556 907
0 582
627 201
697 963
616 608
345 819
810 809
437 706
702 695
448 474
605 474
329 355
691 350
816 231
313 216
864 360
772 278
756 747
529 639
513 525
样例输出
样例输出 1
text
2257.0518296609
样例输出 2
text
3609.92159564177
样例输出 3
text
2195.83727086364
样例输出 4
text
3619.77160684813
数据范围
时间限制：200 ms 空间限制：128 mb
全局限制
- $2\leq M\leq 100$
- $0\leq N \leq 100$
- $0\leq x,y\leq 1000$，且不存在两点重合以及三点共线的情况
部分限制
以下测试不是捆绑测试
- $(\text{5 points})~M=2$
-
$(\text{40 points})~N=1$
-
$(\text{30 points})$ 把绳子刚开始的首尾相连，会形成一个简单多边形（不会与自己相交）
- $(\text{25 points})$ 无限制
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！