从0开始的计算几何（二）———点与线练习题题解

前排提示，本文章内容来源于牛客进阶课程计算几何。（本人仅转述加总结，想要了解更多请点击牛客竞赛课程专栏购买）

本博客为菜鸡转述，如有错误请轻喷，大佬请点击右上角离开。

本次为题目讲解，由于是做题不是搞研究，所以那些比较难证明但是又可以感觉出来的性质，我们都是直接掏出来用的，请原谅本菜鸡，因为证明实在过分繁琐困难了，我就不证直接用了。

首先是题目链接
首先A题，还记得我们前面讲的非数NaN吗,当NaN与任何数字比较的时候，只有不等于操作返回true，所以该题需要我们凑出一个NaN，怎么整出NaN可以百度，这里我们简单的输出 0 0就可以了。

B题，是一个光线回转法的板子题，这个我们稍后再讲，顺便介绍下光线回转法

C题，是一道来自2020ICPC昆明的一题铜牌几何题
题意大概是这样子的，一个点走过一条线段，在线段的同一侧有许多点 $(n\le 1000)(n\; \le \; 1000)$ ，随着时间的推移，从线段上从开始点到结束点看这些点的视角会发生变化。目光可以抽象成一条直线，顺时针扫过整个平面，然后对于每个点进入视野的时间就会有先后顺序。题目会进行若干次询问，当线段上的点走到哪个位置的时候，对于最初的第h个点第k次交换位置的时候，此时线段上的点的位置。
实际就是个直线与线段相交问题，然后你对每个点都做一次遍历，整出n个直线，求出与线段交点然后排序就完事。这题有问题的地方我们不能用叉积去判断点是否在线段上，因为叉积的几何意义是面积是吧，假设我们的线段长度非常非常大，那么一点点精度误差，就能让这个面积很大。所以我们判断是否在线段上用点的横坐标去判断就好了。

D题，后面与光线回转法一起讲

E题，求图形是左手图还是右手图，注意到手掌的底边是最长的，而且这个长度是唯一的，那么我们只要找到这个底边，看底边左右的边就能知道是左手还是右手了

F题，让我们先来回忆下中学知识，假如你要求这个小球反弹后与哪一条边率先相交，你该用什么简单的办法求出来呢。那自然是，以相交边为对称轴翻转啦

我们凭借直觉，是不是可以感觉到时间越短，交点一点最少，那么我们就二分时间，然后判断下交点个数就OK了。

那么我们该如何求出与一条边的相交次数呢，答案自然是不停的翻转啦， 这里借用下别人的图

这样子我们就求出来了与一条边的交点次数，那么与其他两条边的交点次数呢，假设我们旋转三角形，那么与原来某一条边的相交次数就变成了与另一条边的相交次数了，在代码上我们不用真的去旋转三角形，因为方向是相对的对吧，那么我们选择向量方向不是能达到同样的效果，那么这个问题至此圆满解决。

G题，题解为判断一个点是否在三角形内，对三条边做3次toleft测试即可

H题，本场最难题，题意为寻找两个宽度为x的无限长长方形的相交得出的正方形包围所有的点，问x的最小值。首先，我们直觉一下，感觉到最小长度的时候一定有两个点在某一直线上（证明的话请自行证明，或者去轰炸俊杰吧），那么我们二分宽度，求出所有点在该直线上的投影位置，只要这些投影点的距离全部小于x那么就说明宽度为x是可以做到全覆盖的。具体实现比较烦，建议直接去看俊杰代码。

现在来讲D题，寻找多边内最长的一条线段，首先，我们直觉一下，是不是该直线一定经过多边形的两个端点。但是呢，两个端点所在的线段不一定全部在多边形内部是吧。那么我们还要判断一下。这么暴力做的时间复杂度是$n{}^{4}n\{^4\}$，但是由于这个算法不一定能跑满这些时间复杂度，那么你常数优秀的话也是能过的。

那么我们就要想办法降低时间复杂度，请看如下图

如果多边线的边由内向外穿出设为1，由外向内穿设为-1，如果他们的和不为0，那么该段线段一定在多边形外部（直觉感受），再求出每个交点到出发的距离，相减即可得每一段线段的长度，那么这个问题就很好做了。请大伙细细品味D题这个做法

当理解完D题，你就能够理解光线回转法了。
现在给定这么一个问题，给定点与多边形，如何判断点是不是在多边形内部。
假如我们从该点引出一条直线，假如该直线与多边形有偶数个交点，那么我们能够判断这一点在多边形内吗？这种看起来似乎非常正确，但是它无法解决特殊情况，即该直线与某一边重合或者与某个顶点相交了。 所以大牛们想出了另一种方法，回转法，就是以该点为园心，跟着顶点旋转，如果逆时针旋转了一圈，就把圈数+1，当回转数为0的时候，点在多边形外部。（我无法证明这个做法，想看证明的请去查看论文）,那么我们只要求出每次旋转的角度，然后加起来就好了，但是呢，反三角函数是有精度误差的啊，那么我们能不能整出一个没有精度误差的做法。这个时候就该我们的光线回转法登场了。

请回过头去感受D是怎么判断线段是否在多边形内部的，那么我们是不是可以通过这个方法去判断点在不在多边形内部呢，那必然是可以的啊，直线是点的集合，线段是直线的一部分，那么能判断线段在多边形内外的话，那么不就代表能判断线段上的点在多边形内外吗。所以我们直接从点引出一条直线，通过判断穿出穿入，不就直接能判断这个点是否在多边形内部了。
如果你去百度的话，会发现这个做法不仅解决了判断点与多边形的关系，还解决了求解回转数的问题。这也就是光线回转法的核心操作，所以我把D放到最后来讲，希望能对你理解光线回转法有一点帮助（具体请看论文，本菜鸡，真的不会证明啊QAQ）。

值得注意的是,当线段的端点与直线相交的时候，我们需要特殊判断，如果是从下向上并且是上端点或者是从上到下并且为上端点的话，就视为没有相交。 下面贴光线回转法代码

	pair<bool,int> winding(const Point&a)const//返回是否在多边形内与回转数
    {
        int cnt=0;
        for(size_t i=0;i<p.size();++i)
        {
            const Point u=p[i],***xt(i)];
            if(fabs((a-u)^(a-v))<=eps&&(a-u)*(a-v)<=eps)return{true,0};
            if(abs(u.y-v.y)<=eps)continue;
            Line uv={u,v-u};
            if(u.y<v.y-eps&&uv.toleft(a)<=0)continue;
            if(u.y>v.y+eps&&uv.toleft(a)>=0)continue;
            if(u.y<a.y-eps&&v.y>=a.y-eps)cnt++;
            if(u.y>=a.y-eps&&v.y<a.y-eps)cnt--;
        }
        return {false,cnt};
    }

如果有看代码需求的话，请去比赛提交里查看他人的代码（当然你要看本菜鸡的也行）。

后排推销牛客课程

牛客字符串:https://www.nowcoder.com/courses/cover/live/738?coupon=ALL9J4k

牛客计算几何：https://www.nowcoder.com/courses/cover/live/737?coupon=AItgv8H

牛客竞赛数学:https://www.nowcoder.com/courses/cover/live/731?coupon=AY1OGMH

牛客竞赛动态规划:https://www.nowcoder.com/courses/cover/live/435?coupon=As6SCkA

牛客数据结构：https://www.nowcoder.com/courses/cover/live/707?coupon=AdEeRqG