Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ题目分类---计算几何

Posted on 2009-11-22 03:56 Uriel 阅读(1127) 评论(0)  编辑 收藏 引用 所属分类: POJPOJ题目分类

计算几何是为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   最近点对问题,王晓东的书没看懂。。

 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理