Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2月前

04/19
21:47
Delaunay三角剖分 欧几里得最小距离生成树

[2017.04.18 省选模拟赛] 旅行商

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

前面说到moreD在天际里投机倒把赚钱,看着自己的金币蹭蹭往上涨当然是一件令人偷税愉悦(●’◡’●)的事情。
但是考虑到在路上跑的时间成本,整件事情就不那么让人满意了。
moreD共在 N 个城市间倒卖物品。他从 1 号城市出发,自然,这 N 个城市都是要访问到的。
好消息是,moreD装了一个奇怪的mod,可以让他使用飞行坐骑,于是两个城市间的距离就是它们之间的直线距离。
由于moreD玩游戏的时候是个没有耐心的人,他希望最小化在路上最长花费的时间,也就是说,使得在城市间飞行的距离的最大值最小。
moreD明白这应该需要写算法解决,但是由于3D眩晕症,他现在已经脸如死灰地躺在床上了(◎﹏◎),显然不能胜任这个任务。于是他希望你能帮他解决这个问题。
无畏的勇者(没有龙可以屠实在是不好意思了)啊,赶快解决这个问题,把moreD从无尽跑路的深渊中拯救出来吧!

Read More →

[2017.04.18 省选模拟赛] 旅行商

@krydom7月前

12/6
21:20
计算几何

[bzoj 3170] [Tjoi 2013]松鼠聚会

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家去,求走过的最短距离。

Read More →

[bzoj 3170] [Tjoi 2013]松鼠聚会

@krydom1年前

05/25
10:37
计算几何基础

[bzoj 1007] [HNOI2008]水平可见直线

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.

Read More →

[bzoj 1007] [HNOI2008]水平可见直线

@krydom1年前

03/23
20:31
计算几何基础 随机化

[bzoj 2823] AHOI2012 信号塔

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息,这些传感器只与设在集训地中的信号塔进行通信,信号塔接收信号的覆盖范围是圆形,可以接收到所有分布在该集训区域内所有N个小型传感器(包括在该圆形的边上)发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比,因为是野外训练,只能使用事先储备好的蓄电设备,因此在可以收集所有传感器信息的基础上,还应使得信号塔的功率最小。小龙帮助教官确定了一种信号塔设置的方案,既可以收集到所有N个传感器的信号,又可以保证这个信号塔的功率是最小的。同学们,你们知道,这个信号塔的信号收集半径有多大,它应该设置在何处吗?

Read More →

[bzoj 2823] AHOI2012 信号塔

@krydom1年前

03/23
19:57
凸包 计算几何

[bzoj 1670] Usaco2006Oct Building the Moat护城河的挖掘

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 为了防止口渴的食蚁兽进入他的农场,Farmer John决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水,并且,护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水,也就是说,能包围所有的泉水。泉水一定在护城河的内部,或者恰好在河道上。当然,护城河构成一个封闭的环。 挖护城河是一项昂贵的工程,于是,节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下,在满足需求的条件下,护城河的总长最小是多少。 所有泉水的坐标都在范围为(1..10,000,000,1..10,000,000)的整点上,一股泉水对应着一个唯一确定的坐标。并且,任意三股泉水都不在一条直线上。 以下是一幅包含20股泉水的地图,泉水用"*"表示

Read More →

[bzoj 1670] Usaco2006Oct Building the Moat护城河的挖掘