计算几何

• [计算几何]pku1444 长方体旋转      摘要: 用递归旋转法解决长方体表面点的最近表面距离
  
    阅读全文
  posted @ 2008-01-23 21:07 Felicia 阅读(1343) | 评论 (2)  编辑
• [计算几何]pku3293      摘要: 先按规则连。规则是隔一段连一个。比如一条直线上有6个点，就1-2，3-4，5-6，这么连。如果只有奇数个点，就不行。然后再判有没有洞。
  方法是任选一个点，走一圈，看看是否遍历所有的点。
  
    阅读全文
  posted @ 2007-10-22 14:06 Felicia 阅读(591) | 评论 (1)  编辑
• [计算几何]pku3429      摘要: 直接按照题目意思模拟即可。关键是需要实现有理数运算。我的方法是重载运算符。
  
    阅读全文
  posted @ 2007-10-22 13:50 Felicia 阅读(590) | 评论 (3)  编辑
• [计算几何]pku3424      摘要: 先确定窗口左上角可能出现的区域，方法是对每个点确定这样一个区域，然后求交。接下来枚举窗口左上角，计算密码序列，插入一个set中。最后按字典序输出这个set。
  
    阅读全文
  posted @ 2007-10-22 13:48 Felicia 阅读(411) | 评论 (0)  编辑
• [计算几何]pku1379      摘要: 平面点的三角剖分应用。对输入点集进行三角剖分，求得对偶图Voronoi图，Voronoi图的结点以及边与矩形的边的交点就是可疑点。枚举可疑点，计算最优值就是答案。
  
    阅读全文
  posted @ 2007-10-10 09:31 Felicia 阅读(1324) | 评论 (4)  编辑
• [计算几何]两个凸多边形的交      摘要: 两个凸多边形的交
  
    阅读全文
  posted @ 2007-10-07 10:27 Felicia 阅读(1713) | 评论 (2)  编辑
• [计算几何]pku3407      摘要: 简单的几何题，先把经纬度换算成球面坐标，再把球面坐标换算成直角坐标，然后求夹角，乘半径得到球面距离
  
    阅读全文
  posted @ 2007-10-02 17:55 Felicia 阅读(614) | 评论 (1)  编辑
• [计算几何]pku3410      摘要: 我的做法是，枚举第一个多边形的第i条边和第二个多边形的第j条边重合，然后从这条重合的边开始，尽可能的向后扩展重合边，然后判断剩下的多边形是否是凸多边形。
  比赛的时候，我在某个地方忘记对多边形点数求模，导致wa了很久，一直到比赛结束后才AC。以此为鉴！
  
    阅读全文
  posted @ 2007-10-02 17:52 Felicia 阅读(610) | 评论 (0)  编辑
• [计算几何]pku3391      摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
  平面欧几里德最小生成树是经典问题，可以做到O(nlogn)。具体做法是先对平面点进行三角剖分，时间复杂度是O(nlogn)，三角剖分的边就是可能的在最小生成树的边。因为是平面图，所以有O(n)条边，在其上应用 Kruscal 算法即可。
  
    阅读全文
  posted @ 2007-09-28 20:17 Felicia 阅读(777) | 评论 (0)  编辑
• [计算几何]pku1673      摘要: 此问题可转化为求三角形垂心。我的做法是设垂心坐标为(x, y)，然后利用垂直关系解方程。
  
    阅读全文
  posted @ 2007-09-27 17:18 Felicia 阅读(652) | 评论 (1)  编辑
• [计算几何]平面点的曼哈顿最小生成树      摘要: 平面点的曼哈顿最小生成树
  
    阅读全文
  posted @ 2007-09-27 14:48 Felicia 阅读(1261) | 评论 (0)  编辑
• [计算几何]pku1624      摘要: 简单计算几何，我的做法是列出所有可能的切法（一共18种），求最优值。
  
    阅读全文
  posted @ 2007-09-26 20:46 Felicia 阅读(572) | 评论 (1)  编辑
• [计算几何]pku1408      摘要: 构造所有的线段，然后枚举每对水平－竖直线段，求交点，然后计算四边形面积，求最大值。
  
    阅读全文
  posted @ 2007-09-25 21:59 Felicia 阅读(621) | 评论 (0)  编辑
• [计算几何]pku3384      摘要: 强烈推荐此题。半平面交算法的一个应用。
  具体做法是，把多边形的每条边向内平移r单位长度，用这些线段所在直线和原多边形作半平面交，得到的区域就是半径为r的圆放入多边形的可行域。可以证明这个区域一定是凸的，或者退化为一条线段，或一个点。那么，我们就可以在这个区域上求最远点对啦。
  我的做法是O(n^2)的。应该存在O(nlogn)的做法，因为都是凸多边形，每次半平面交只有最多两个交点，可二分，而最后的求最远点对可以旋转卡壳。比赛的时候时间少，就写了个暴力O(n^2)的。
  
    阅读全文
  posted @ 2007-09-23 16:19 Felicia 阅读(786) | 评论 (0)  编辑
• [计算几何]pku1410      摘要: 基本几何题，判断线段是否与矩形相交。转化为线段在矩形内或线段与四条边相交。
  唯一要注意的是题目中关于左上角和右下角的定义。
  
    阅读全文
  posted @ 2007-09-22 10:58 Felicia 阅读(527) | 评论 (0)  编辑

Full 计算几何 Archive