zcmimi's blog

arrow_back计算几何共2篇文章

avatar
zc
2020-10-20 16:36:54

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

只用一个矩形的当然很容易求

用两个矩形的话:

先把所有点按x坐标排序,提前记录从前数和从后面数的最大的坐标和最小的坐标(x,y都要)

枚举断开的位置,记录最小值

计算按y轴方向断开的方式一样,把x,y交换后如法炮制就可以了

tip:

记录坐标最小值时要把坐标初始化为- \infty,要开long\ long,要不然会出锅

1/1
Search
search