计算几何
关注
分享
扫一扫
文章平均质量分 87
Albafica
研究生
方向：计算机网络
个人描述：完全没入门。SDN门外汉。痛苦的转型期。
展开
-
POJ2187 Beauty Contest 旋转卡壳
先求凸包，然后旋转卡壳输出最远点对的距离的平方Beauty ContestTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 24459 Accepted: 7467DescriptionBessie, Farmer John's prize co原创 2013-08-05 21:07:42 · 478 阅读 · 0 评论 -
POJ1264 SCUD Busters 凸包
先求多个凸包，算出面积然后给你几个炸弹，如果掉在一个凸包里面就把这个凸包面积加上，每个凸包用一次SCUD BustersTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 625 Accepted: 269DescriptionSo原创 2013-07-25 22:11:48 · 529 阅读 · 0 评论 -
POJ2540 Hotter Colder 半平面交
半平面交,求可行区域的面积。题目中求两点连线的中点形成的中垂线。再进行切割Hotter ColderTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2079 Accepted: 860DescriptionThe children's game原创 2013-07-23 21:21:42 · 609 阅读 · 0 评论 -
POJ1755 Triathlon 半平面交
利用半平面交判断不等式是否有解TriathlonTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 4489 Accepted: 1112DescriptionTriathlon is an athletic contest consistin原创 2013-07-23 21:19:59 · 572 阅读 · 0 评论 -
POJ3384 Feng Shui 半平面交
求多边形内圆最大覆盖的方法 半平面交 向内推进r 求最远点对Feng ShuiTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 3667 Accepted: 1125 Special JudgeDescriptionFeng s原创 2013-07-23 21:17:11 · 698 阅读 · 0 评论 -
POJ3525 Most Distant Point from the Sea 半平面交
半平面交+二分 向内推进 求多边形内切圆半径Most Distant Point from the SeaTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 3433 Accepted: 1571 Special JudgeDescripti原创 2013-07-23 21:14:44 · 630 阅读 · 0 评论 -
POJ1265 Area
PICK定理AreaTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 4175 Accepted: 1896DescriptionBeing well known for its highly innovative products,原创 2013-07-22 00:11:15 · 613 阅读 · 0 评论 -
POJ1385 Lifting the Stone
算重心Lifting the StoneTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 2094 Accepted: 763DescriptionThere are many secret openings in the floor原创 2013-07-21 22:17:18 · 448 阅读 · 0 评论 -
ZOJ1081 Points Within
判断点在一个凸多边形里面Points WithinTime Limit: 2 Seconds Memory Limit: 65536 KBStatement of the ProblemSeveral drawing applications allow us to draw polygons and almost all of them allo原创 2013-07-21 22:00:03 · 419 阅读 · 0 评论 -
POJ3798 Cave Crisis 计算几何+最短路
题目让你求一个最大的圆，能从隧道起点到终点，中间有很多障碍。此题有一个注意点就是终点位置不必满足枚举的距离。判断了就是哇哇哇。还有就是起点到其他边或者多边形的距离除了覆盖接触也不行。二分枚举圆的半径，然后更具枚举的半径建图求最短路即可Cave CrisisTime Limit: 1000MS Memory Limit: 65536K原创 2013-07-21 00:56:01 · 716 阅读 · 0 评论 -
POJ1584 A Round Peg in a Ground Hole 计算几何
简单计算几何A Round Peg in a Ground HoleTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 4439 Accepted: 1363DescriptionThe DIY Furniture company specia原创 2013-07-20 23:58:45 · 634 阅读 · 0 评论 -
CEOI2000 LandsScape 贪心+计算几何
RLJ黑书p13页例题2 书上讲的非常清楚了，不再说了只是注意线段相交的情况要排除一个点在线段上的情况。 还好1Y，这种题目WA了就注定悲剧。计算几何之类的要查好半天的。 题目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2881 2881: [Ceoi2000] LandsScapeTime Limi原创 2013-05-06 23:58:57 · 679 阅读 · 0 评论 -
POJ1113 Wall
刻意用卷包裹法写了一个凸包问题。WallTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 22839 Accepted: 7492DescriptionOnce upon a time there was a greedy King who ordered原创 2012-07-30 19:02:43 · 485 阅读 · 0 评论 -
POJ1039 Pipe
这道题比较简单，就是不要吧上图中第一种情况漏判就可以了。另外最长的路线一点是由一个上方的点，和下方的点组成的直线。只要枚举每一种情况，再从第一个管道开始判断是否存在交点，如果存在则和当前的最大值，比较即可PipeTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 7326 Accep原创 2012-07-29 22:30:07 · 962 阅读 · 0 评论 -
POJ2826 An Easy Problem?!
这是一道细节题。题目中让我们用两条线段接雨水，雨水是垂直落下的，问我们用给定的两条线段能接到多少水。这里用很多种情况都要一一讨论。1：两条线段不想交的时候接不到雨水2：两条线段重合的时候接不到雨水3：两条线段的交点与期中一条线段的最高点相同时，无法接到雨水4：有一条线段水平时接不到雨水。5：当两条线段的最高点均在交点一侧时，期中较高的点遮住了较低的点时，无法接住雨水。原创 2012-07-29 16:54:07 · 1320 阅读 · 0 评论 -
POJ1556 The Doors
这道题目在黑皮书上有。思路很容易就想到，就是枚举每两个端点，判断两个点之间是否与墙相交，不想交的话则将路径距离加入矩阵中，相交的的话则赋值INF，然后就是一个求最短路径的问题，可以用dijkstra算法。这道题麻烦在建图。The DoorsTime Limit: 1000MS Memory Limit: 10000KTot原创 2012-07-28 01:12:55 · 939 阅读 · 0 评论 -
POJ2398 Toy Storage
简直和2318一模一样，唯一的区别就是得排序，和输出的是统计的数据。方法还是一样二分+叉积Toy StorageTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2491 Accepted: 1427DescriptionMom and dad have原创 2012-07-25 16:38:35 · 689 阅读 · 0 评论 -
POJ2318 TOYS
叉积+二分当物品在直线右侧，叉积大于0，在直线左侧叉积小于0.TOYSTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 7249 Accepted: 3426DescriptionCalculate the number of toys that lan原创 2012-07-25 16:04:31 · 800 阅读 · 4 评论