今天算是把半平面交的nlogn版本搞出来了

也做了一些半平面交的经典题

最重要的是感受到了 计算几何的精度的深深的恶意

nlogn的做法 和凸包类似 维护一个直线的双端队列

极角排序后每次加入一条直线都从队首队尾弹出无效直线

在加入时和队尾直线产生交点

最后队首队尾产生交点

中间还有当队尾两直线向量共线时的问题需要处理一下

总感觉 n^2的做法虽然慢 但是精度似乎比nlogn的要靠谱

计算几何很多特殊情况的处理让人很蛋疼

poj 3335 模板

试了下 nlogn 和 n ^ 2板子

其他比较简单的不再说

POJ 3525

让你求一个距离凸多边形内部到边界距离最远的点

很经典的做法

我们二分距离 d

然后把多边形的边界 都向内侧推移d

再看他有没有核（一个点也行）

很显然 核存在意味着 >=d的点存在

问题就结束了

poj 3384

给你一个凸多边形

问用两个固定半径的圆怎样覆盖尽可能多的多边形内部

（圆可以重叠， 圆在多边形内 不能和多边形交，或者包含它）

（数据保证有解）

很显然 这两个圆最后的位置一定是与多边形相切

那我们想上一题类似的把多边形边界向内推移R的距离

核就是圆心的合法放置区域

我们尽量不让圆重叠

所以选取核的距离最远点

数据范围很小

没必要旋转卡壳 直接枚举顶点即可

poj 1755

铁人三项 每个人有三个速度 ai,bi,ci

问有没有一种分配策略来分配三项比赛的路程，使第i个人用时最短 (不能并列)

乍看可能和半平面交比较远

但是转换一下

假如 我们让i最先到达终点 x,y,z为三项比赛长度(x>0, y >0 , z > 0)

总有 x/ai + y/bi + z/ci < x/aj + y/bj + z/cj 对 i != j 成立

整理一下 (1/aj - 1/ai) * x + (1/bj - 1/aj) *y + (1/cj - 1/ci) * z > 0

在z>0时 (1/aj - 1/ai) * x / z+ (1/bj - 1/aj) * y / z + (1/cj - 1/ci) > 0

然后就很明显了 再加上 x/z > 0  y/z > 0

需要注意的是 转化后 X Y是比值 因此 x, y ,z均为负数也可能成立

光限制 x/z > 0 y/z >0 也无用

其实先处理出 三项均大于等于 三项均小于 就不会出现全负的情况了

白书上 是默认 总路程为1 这样就可以更清晰地解决这个问题 （再加上 x + y < 1的约束）

但是写的过程中出现了很多问题 让我很难受

1) 点赋值时 写成了 (x, y)  其实是 (Point) {x, y}

2) poly 和 p数组经常混淆 尤其是求面积时

3）inf和eps 可能需要随着问题调整 看数据范围 还有N不要忘记范围

4）在判断无核时一是用面积 而是直接看返回值 nlogn看返回值还比较稳 n ^ 2可能会留下非法点 面积吧

     一些条件 退化为线段 或 点也可以 要注意

5）我实在搞不懂1755 nlogn为啥会在少判断的情况下tle 可能使垂直的线 在极角排序时的k引入了问题

　但实在不好解决 以后在效率足够的情况下 尽量避免用nlogn

明天任务：

看到了半平面交 最后一个推荐题目

Poj 2540 做法应该是中垂线的线性规划区域 明天写一下

明天有时间 就再开第五部分了 是扫描线一类的东西

计算几何学习5