9
12
2015
0

论逗逼的自我修养之计算几何练习记

嘛..我也想切计算几何题和切菜一样..然而现在做道计算几何题和感觉和剁手一样..

最近也是因为搬原题的事情搞得心情很不爽..第一,我不知道这套题是做交流训练的;第二,我自己出题肯定也没有搬的题质量高;第三,你们自己考出来的分数那么低还来和我BB是原题?所以只能说某学校的小哥们不懂事..所以还是下定决心来学习一点计算几何姿势以后和贵校交流训练的时候就来个三道原创码农计算几何好咯..

也是懒得标记现在做了几题了..反正估计写个五六题等集训队作业下来了就弃坑了吧..我自己的打算是先把白书上的练习做个一些吧..

【UVa 11168】Airport 白书例题,先建出凸包,然后直线一点和凸包的边重合,所以枚举凸包的每一条边,然后用点到直线的距离公式算出来距离和就好了。

【LA 4728】Square 白书例题,旋转卡壳裸题。

【LA 3890】Most Distant Point from the Sea 白书例题,先二分答案,那么到一个点距离大于等于答案的点可以表示成一个半平面,然后就可以用半平面交来判定了。

【LA 2218】Triathlon 白书例题,枚举每一个人来判定,然后假设总长度为1,其中两段长度为[tex]x[/tex]和[tex]y[/tex],那么选出的人比另一个人跑得快的条件可以看成一个半平面,于是就可以用半平面交来判断它是否可以跑的比所有人快。

【LA 4992】Jungle Outpost 白书例题,最优的轰炸方案一定炸连续的一段,于是就可以二分答案然后用半平面交来判定是否存在一个位置无论怎么炸都能受到保护。

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 1193

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com