计算几何是为Regional临时抱佛脚搞的。。还很菜。。大牛们多指教。。
评述的话主要是自己以后找起题来方便。。大牛们忽略就好。。
1031 求多边形累计偏转角。。抄啊抄。。
1039 点积叉积应用。。自己的死活过不了。。计算几何啊。。。
1066 方法是枚举目标点到边上每两点中点构成的线段,找与其他线段相交数最少的
1106 判断半圆最多覆盖多少点
1113 简单凸包。。凸包周长加半径L圆的周长。。
1127 并查集+线段相交
1151 坐标离散化加扫描线,第一次了解。。
1228 凸包唯一确定问题。。Discuss什么都说了。。
1244 不要想复杂。。O(n^3)+正常建坐标系就过了。。
1265 求顶点为整数的任意多边形内部整点数(Pick定理),边上整点数(GCD),面积(叉积)
1266 求能覆盖一条弧的最小矩形面积,矩形顶点是整点
1279 直接贴的半平面交模板。。
1319 应该算是简单几何。。注意边长小于1 的情况
1329 浙大模版真好用。。,但是这题输出被我改得好恶心
1380 计算几何,判断小矩形能否放进大矩形。。可旋转。。
1389 类似1151
1410 判断矩形与一线段是否相交,注意线段在矩形内部的情况
1473 求首尾两点距离。。比较水
1474 半平面交求核面积抄模板死活过不了。。无奈抄了神奇的标程。。
1584 判凸边形,计算点到凸包边上最小距离,判点在凸包内
1654 求多边形面积。。抄公式。。
1696 叉积判断是顺时针还是逆时针方向,点积
1673 直接抄的浙大模版。。一次AC。。好爽。。。
1859 分奇偶按左右分别不同方向排序,看能否配对
1927 不难,因为没考虑只能围成一个小圆的情况WA无数次。。
1940 很久以前做完1939就看了这个,,没注意顶点是奇数的条件。。死活想不出。。。
1971 找每两个点的中点,排序。。数构成的平行四边形数
1981 求落在单位圆里的点数。。枚举。。
2002 给若干点,求构成多少正方形。。枚举两点二分查找是否有符合条件的另两点
2007 不懂自己按tan排序为什么错。。实在受不了。。抄了网上一个不太懂的算法。。
2079 用原始的凸包模板TLE无数次,再优化只能到WA。。ft。。。传说中的旋转卡壳好强大。。勉强理解了。。自己还写不出
2187 凸包。。抄浙大模板。。
2208 已知六边求三棱锥体积。。抄公式。。。
2354 算地球上两点距离。。经纬度形式给出。。地理没学好。。抄了部分代码。。
2318 叉积判断同侧。。二分确定区间
2398 同2318,做一送一
2546 求两圆相交的面积,用到海伦公式
2653 链表+线段相交。。。第一次完全自己写链表。。搞得想吐血
2780 类似3512
2954 类似1265 ,求三角形内部整点数,Pick定理
2957 以为是简单的几何题,这题做的人好少。。没想到还要用坐标旋转什么的。。第一次做计算几何
3130 半平面交求多边形核的存在性。。ZZY大牛的论文看过。。写不出来。。模板不太懂。。超长的模板。。7174B。。。
3304 判断直线和线段相交
3335 跟3130不同的另一个半平面交模板。。
3348 求凸包面积。。函数全部来自浙大模板。。看来浙大模板很强悍。。没Discuss种种错误
3407 类似2354,已知两点经纬求距离
3432 同2002
3512 枚举斜率+sort。。。抄的别人的思路。。类似1118.。但是O(n^3)必挂。。。
3565 貌似是匹配的问题。。上网搜了个用计算几何调整法过的。。过程类似交换排序
3608 求凸包间最小距离,旋转卡壳。。很强大
3714 最近点对问题,王晓东的书没看懂。。