开篇碎碎念
马上就要正式迎接新的大一生活啦，学个计算几何助助兴bushi
感觉还算不上入门，但是做着玩啦
还不知不觉的完成了牛客的100AC
做题小总结
是按照洛谷用户分享题单：计算几何——从入门到跳楼 https://www.luogu.com.cn/training/16408来逐步完成的，现在已经完成基础part啦。总的来说这个题单还是有点好玩的（
那就看看都写了些什么题目叭
P1652 圆
- 题目链接： https://www.luogu.com.cn/problem/P1652
- 思路：可以画曲线，意味着可以把无关的圆都避开。那么题目就变成了，有多少个圆将这两个点分开（一个在里一个在外）。
- KEY WORK：分别计算两点到圆心的距离，并与半径判断
- 优化：用平方代替开根号，避免误差，减小计算量
P2181对角线
- 题目链接：https://www.luogu.com.cn/problem/P2181
- 思路：每个交点都与四个顶点有关，所以原题目就是从n个顶点里面选择四个顶点，简单的组合数公式就可以得到结果啦
- 优化：边乘边除，将 n * (n-1) * (n-2) * (n-3) / 24 改成n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4 。从而避免爆ll
P1257 平面上的最接近点对
- 题目链接：https://www.luogu.com.cn/problem/P1257
- 思路：n^2暴力
- 优化：
1.当某个方向的距离过大的时候把循环break掉（事先排序）
2.用平方代替距离
P1142轰炸
- 题目链接：https://www.luogu.com.cn/problem/P1142
- 思路：本题要求的是一条直线最多能覆盖的最多的点数，过一个点，斜率一定的直线只有一条。所以固定一个点，看其他点和该固定点所连成的直线的斜率是多少，用map去存，找到斜率相同最多的条数
- warning：map记得要清空
P2180 摆石子
- 题目链接：https://www.luogu.com.cn/problem/P2180
- 思路：感觉还是和计算几何没什么太大联系，通过实践发现，摆放成最多有一行不完整的矩形，可以围成的矩形个数最多。且nm的矩形最多可以构成 n(n-1)/2 *m *(m-1)/2个子矩形。 那么就暴力枚举看看每一行放多少个
P1355 神秘大三角
*题目链接：https://www.luogu.com.cn/problem/P1355
*思路：题面很干净清楚，就是判断一个点与一个给定三角形的位置关系。二维计算几何的基础题了，那么就分别判断几种情况：最好判断的是当这个点与顶点重合的时候：那么很显然就是判断坐标是否相同；对于判断是否在三角形边上，我是选择了判断这个点与其中两个顶点所连成的直线是否平行，还要特别判断一下是不是在延长线上；而对于三角形内外的话则是用的点积。
看了题解知道了一些新的东西：例如海伦公式：利用三角形的三条边的边长直接求三角形面积的公式：S=√p(p-a)(p-b)(p-c)。当该点与顶点构成的三个三角形里面，存在有一个面积为零，那么就在三角形边上或者定点上，这三个三角形的面积与大三角形面积相等，那么就在三角形内部，当构成的三角形面积大于原三角形时，在三角形外部。
除了海伦公式之外还有用叉积来计算的：
我们想到向量的叉积可以得到两个向量之间的有向面积，我们还知道向量叉积可以求出多边形的面积（就是把有向面积加一起啦），思考求多边形面积的原理，可以想到通过判断有向面积的正负来判断点是否在三角形内。
我们发现，如果点在三角形边上，那么一定会有某一个向量叉积答案为0，我们可以通过判断向量叉积是否为零来判断是否有点在边上。
注意：
我们知道，当向量夹角小于0的时候，叉积是负的。因此当所有的有向面积同正或同负时，点都在三角形内部。
其实，如果点在边的同一直线上时，叉积也为零，我们可以通过点到线段两边的端点的两个向量是否同向来判断是否在线段上，这可以用向量的点积来判断。
P1325雷达安装
- 题目链接：https://www.luogu.com.cn/problem/P1325
- 思路：贪心的放置。把岛屿坐标转换为x轴的线段。记得排序。