- 浏览: 584051 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
接上文:学习凸包(二):分治法求解http://128kj.iteye.com/blog/1748622
通过前面两文学习,基本上明白了凸包,先做个练习POJ 1113.
POJ 1113题意:
从前有一个吝啬的国王要求他的总设计师在他的城堡周围建一道围墙。这国王非常吝啬,以至于他没有听总设计师的建一个拥有外形漂亮又高大的砖头塔楼的围墙的建议,而是要求用最少的石头和劳工围着整个城堡建围墙,但是要求围墙必须远离城堡一定的距离。要是国王发现发现设计师用了超过建造围墙所需要的材料,那么这个设计师的脑袋将保不住了。而且,国王要求设计师马上拿出一个建墙的计划,列出建造围墙所需要的最少的材料。你的任务是去帮助这个可怜的设计师保住他的性命,请写一个程序算出建造满足国王要求的围墙的最小的长度。这个任务事实上稍微有点简单,因为国王的城堡是一个多边形的,除开顶点处,其他的地方不会相交,并且位于平坦的地面上,设计师早已画好了一个笛卡尔坐标系,而且精确地计算出了城堡中每一个点的坐标。
Input
第一行包括两个整数,N,L,第一个整数是点的个数,第二个整数是围墙必须远离城堡的距离。接下来n行,每行两个数{中间一个空格}表示每一个点的坐标。所有的点各不相同。
Output
输出一个整数,即围墙的长度。答案四舍五入
样例:
Sample Input
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Sample Output
1628
从图可以看出,所求围墙(虚线部分)长度 = 凸包边长 + 一个圆周长
下面是AC代码(分治法求凸包):
源码:
通过前面两文学习,基本上明白了凸包,先做个练习POJ 1113.
POJ 1113题意:
从前有一个吝啬的国王要求他的总设计师在他的城堡周围建一道围墙。这国王非常吝啬,以至于他没有听总设计师的建一个拥有外形漂亮又高大的砖头塔楼的围墙的建议,而是要求用最少的石头和劳工围着整个城堡建围墙,但是要求围墙必须远离城堡一定的距离。要是国王发现发现设计师用了超过建造围墙所需要的材料,那么这个设计师的脑袋将保不住了。而且,国王要求设计师马上拿出一个建墙的计划,列出建造围墙所需要的最少的材料。你的任务是去帮助这个可怜的设计师保住他的性命,请写一个程序算出建造满足国王要求的围墙的最小的长度。这个任务事实上稍微有点简单,因为国王的城堡是一个多边形的,除开顶点处,其他的地方不会相交,并且位于平坦的地面上,设计师早已画好了一个笛卡尔坐标系,而且精确地计算出了城堡中每一个点的坐标。
Input
第一行包括两个整数,N,L,第一个整数是点的个数,第二个整数是围墙必须远离城堡的距离。接下来n行,每行两个数{中间一个空格}表示每一个点的坐标。所有的点各不相同。
Output
输出一个整数,即围墙的长度。答案四舍五入
样例:
Sample Input
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Sample Output
1628
从图可以看出,所求围墙(虚线部分)长度 = 凸包边长 + 一个圆周长
下面是AC代码(分治法求凸包):
import java.util.*; class Line {//线 Point p1, p2; Line(Point p1, Point p2) { this.p1 = p1; this.p2 = p2; } public double getLength() { double dx = Math.abs(p1.x - p2.x); double dy = Math.abs(p1.y - p2.y); return Math.sqrt(dx * dx + dy * dy); } } class Point{//点 double x; double y; public Point(double x,double y){ this.x=x; this.y=y; } } /* * 分治法求凸包 */ class QuickTuBao { List<Point> pts = null;//点集 List<Line> lines = new ArrayList<Line>();//点集pts的凸包 public void setPointList(List<Point> pts) { this.pts = pts; } public QuickTuBao(List<Point> pts){ this.pts=pts; } //求凸包,结果存入lines中 public List<Line> eval() { lines.clear(); if (pts == null || pts.isEmpty()) { return lines; } List<Point> ptsLeft = new ArrayList<Point>();//左凸包中的点 List<Point> ptsRight = new ArrayList<Point>();//右凸包中的点 //按x坐标对pts排序 Collections.sort(pts, new Comparator<Point>() { public int compare(Point p1, Point p2) { if(p1.x-p2.x>0) return 1; if(p1.x-p2.x<0) return -1; return 0; } }); Point p1 = pts.get(0);//最左边的点 Point p2 = pts.get(pts.size()-1);//最右边的点,用直线p1p2将原凸包分成两个小凸包 Point p3 = null; double area = 0; for (int i = 1; i < pts.size(); i++) { p3 = pts.get(i); area = getArea(p1, p2, p3);//求此三点所成三角形的有向面积 if (area > 0) { ptsLeft.add(p3); } else if (area < 0) { ptsRight.add(p3); } } d(p1, p2, ptsLeft);//分别求解 d(p2, p1, ptsRight); return lines; } private void d(Point p1, Point p2, List<Point> s) { //s集合为空 if (s.isEmpty()) { lines.add(new Line(p1, p2)); return; } //s集合不为空,寻找Pmax double area = 0; double maxArea = 0; Point pMax = null; for (int i = 0; i < s.size(); i++) { area = getArea(p1, p2, s.get(i));//最大面积对应的点就是Pmax if (area > maxArea) { pMax = s.get(i); maxArea = area; } } //找出位于(p1, pMax)直线左边的点集s1 //找出位于(pMax, p2)直线左边的点集s2 List<Point> s1 = new ArrayList<Point>(); List<Point> s2 = new ArrayList<Point>(); Point p3 = null; for (int i = 0; i < s.size(); i++) { p3 = s.get(i); if (getArea(p1, pMax, p3) > 0) { s1.add(p3); } else if (getArea(pMax, p2, p3) > 0) { s2.add(p3); } } //递归 d(p1, pMax, s1); d(pMax, p2, s2); } // 三角形的面积等于返回值绝对值的二分之一 // 当且仅当点p3位于直线(p1, p2)左侧时,表达式的符号为正 private double getArea(Point p1, Point p2, Point p3) { return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y - p3.x * p2.y - p2.x * p1.y - p1.x * p3.y; } } public class Main { //计算凸包周长+圆周长 private static int getLength(List<Line> ls, int d) { double length = 0.0; Line l1 = null; for (int i = 0; i < ls.size(); i++) { l1 = ls.get(i); length += l1.getLength(); } length += 2 * d * Math.PI; return (int)(length + 0.5); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int d = cin.nextInt(); List<Point> pts = new ArrayList<Point>(n); int x, y; for (int i = 0; i < n; i++) { x = cin.nextInt(); y = cin.nextInt(); pts.add(new Point(x, y)); } QuickTuBao qt = new QuickTuBao(pts); List<Line> ls = qt.eval(); int length = getLength(ls, d); System.out.println(length); } }
源码:
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3663题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1527POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2982POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1849题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1594关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1831POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)
2012-12-22 13:57 1525一种形象的理解是 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1564分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(四):Graham 扫描法
2012-12-17 16:33 2203Graham扫描法 基本思想:通过设置一个关于候选点的 ... -
学习凸包(二):分治法求解
2012-12-16 14:32 3376接上文:学习凸包(一):暴力算法求解http://128kj. ... -
学习凸包(一):暴力算法求解
2012-12-15 17:06 2050凸包:令S是平面上的一个点集,封闭S中所有顶点的最小凸多边 ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1355接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1767关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1674关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1751关于树状数组,请参考:http://128kj.iteye.c ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1749213
北大POJ1113-Wall【凸包】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1752345
凸包melkman算法cpp实现,通过poj1113题测试
O(nlogn)凸包问题 poj2187
poj1113 melkman算法求凸包, 使用STL
POJ上做的一个凸包的题,可作为凸包的模板。
1.16.2 直线旋转_两凸包的最短距离(poj3608) 58 1.16.3 扇形的重心 62 1.16.4 根据经度纬度求球面距离 62 1.16.5 多边形的重心 64 1.16.6 存不存在一个平面把两堆点分开(poj3643) 66 1.16.7 pku_3335_判断多边形的核...
5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) 7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式. 8. 调用系统的qsort, 技巧很多,慢慢掌握. 9. 任意...
3.6.4 凸包 3.6.5 数值积分 3.7 一起来挑战GCJ的题目(2) 3.7.1 Numbers 3.7.2 No Cheating 3.7.3 Stock Charts 3.7.4 Watering Plants 3.7.5 Number Sets 3.7.6 Wi-fi Towers 第4章 登峰造极——高级篇 4.1 更加...
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...