Skip to content

1262: SimplePhysics

题目

题目描述

《简单物理学/SimplePhysics》是一款物理/力学为基础的游戏,可惜这款游戏已经停更多年。作者也早已开发出《SimpleRockets》以及《SimplePlanes》等高度物理仿真的游戏续作。特别是在《简单火箭》的游戏中,不会造轮船的汽车设计师不是好的飞行员……

在一张无限大木桌上,有 $N$ 个钉子一根绳子,绳子的两端从桌上的两个孔洞中穿了过去。现在,从桌下拉紧绳子的两端,绳子会慢慢收紧,直到所有地方都绷紧不能移动。你的任务是求出最终留在桌面上的绳长。

我们将会用多条线段来描述这根绳子的初始状态,并且保证初始状态的绳子不会接触到任何一个钉子。

你可以参考以下的三个例子来了解这一个拉伸的过程:

  • 图1

截屏2021-07-12 22.54.15

  • 图2

截屏2021-07-12 22.56.03

  • 图3

截屏2021-07-12 22.56.38

输入格式

第一行是两个整数 $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$,且不存在两点重合以及三点共线的情况

部分限制

以下测试不是捆绑测试

  1. $(\text{5 points})~M=2$
  2. $(\text{40 points})~N=1$

  3. $(\text{30 points})$ 把绳子刚开始的首尾相连,会形成一个简单多边形(不会与自己相交)

  4. $(\text{25 points})$ 无限制

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!