logo AlgoBeat OnlineJudge
登录 注册

#101159. [BZOJ 1159] [CTSC2005]孤独的牧羊女dalarna

内存限制:162 MiB 时间限制:100000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

在瑞典的达拉纳洲有一座高山。山上有一个小屋,里面住着一位牧羊女。每天清晨,隔壁的山头会传来一阵悠扬的 长笛声,而牧羊女则会站在屋里用自己的歌声回应。小屋的俯视图是一个有 个顶点的简单多边形,每一面墙可以 反射声音,但是由于不可避免的能量损失,最多只能反射 次( 表示不能反射声音)。墙面非常光滑,因此声音 的反射遵循反射角等于入射角,如图 1。墙角不能反射声音,而每面墙的其他部分即使离墙角很近都可以 反射声音。

突然有一天,牧羊女问自己:在小屋的哪些地方能听到她的歌声?假设所有听众都在屋里靠墙而坐,那么歌声能到达的墙一共有多长?图 2 的四幅示意图分别画出了初始情况和声音经过 次反射后到达的区域。灰色部分表示能听到歌声的部分,黑点表示牧羊女的位置。本题所求即灰色部分在多边形边界上的总长度。

输入格式

第一行包含四个整数 分别表示小屋的墙角数、最多反射的次数以及牧羊女的坐标(牧羊女所在位置保证在屋内且至少离墙 个单位)。

以下 行每行两个整数 ,表示第 个墙角的坐标。

墙角按照顺时针或逆时针排列。

输出格式

输出文件仅包含一个实数 ,表示能听到歌声的墙的总长度。保留两位小数。

样例

样例输入 #1

5 0 100 135
20 200
200 100
300 125
40 10
100 100

样例输出 #1

469.86

样例输入 #2

8 1 25 15
0 0
0 20
30 20
30 0
20 0
20 10
10 10
10 0

样例输出 #2

106.67

数据范围与提示

,所有坐标为绝对值不超过 的整数。

的数据满足

鸣谢刘汝佳先生授权使用