`
128kj
  • 浏览: 601653 次
  • 来自: ...
社区版块
存档分类
最新评论

学习凸包(三):凸包练习 POJ 1113

阅读更多
接上文:学习凸包(二):分治法求解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代码(分治法求凸包):
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);
  }
}


源码:
  • 大小: 1.1 KB
0
0
分享到:
评论

相关推荐

    凸包练习: POJ 2187(JAVA)

    总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...

    POJ1113-Wall【凸包】

    【标题】"POJ1113-Wall【凸包】"所指的是一道来自北京大学在线判题系统POJ的编程题目。该题目主要涉及计算机科学中的算法问题,特别是几何算法中的“凸包”概念。 【描述】"北大POJ1113-Wall【凸包】解题报告+AC...

    ACM常用算法及其相应的练习题 (2).docx

    ACM常用算法及其相应的练习题 本资源摘要信息涵盖了ACM常用的算法和相应的练习题,旨在帮助程序员和算法爱好者快速学习和掌握这些算法。下面详细介绍这些算法和练习题。...(4) 凸包:poj2187, poj1113

    ACM常用算法及其相应的练习题.docx

    * 凸包:poj2187, poj1113 中级部分: 一、基本算法 * C++的标准模版库的应用 + poj3096, poj3007 * 较为复杂的模拟题的训练 + poj3393, poj1472, poj3371, poj1027, poj2706 二、图算法 * 差分约束系统的...

    学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)

    在本文中,我们将深入探讨“学习凸包(五):卷包裹算法——兼解POJ1113(JAVA)”这一主题。凸包是计算机图形学、算法和数据结构领域中的一个重要概念,它指的是在一组点集中,由这些点构成的最小外接多边形。在解决...

    poj题目分类

    poj题目分类 POJ(Princeton Online Judge)是一個在线编程平台...4. 凸包:例如 poj2187、poj1113。 这些知识点涵盖了算法、数据结构、数学、计算几何学等领域的多个方面,为编程爱好者和学生提供了广泛的知识基础。

    ACM常用算法及其相应的练习题 (2).pdf

    例题:poj2187、poj1113。 中级 一、基本算法 * C++的标准模版库的应用:C++的标准模版库是指C++语言的标准库,提供了许多有用的算法和数据结构。例题:poj3096、poj3007。 * 较为复杂的模拟题的训练:较为复杂的...

    ACM 新手指南 PKU 题目分类

    - **凸包**:构建凸包并求解相关的几何问题。 - 示例题目:POJ 1837, POJ 1276 - **线段树与树状数组**:适用于解决区间更新与查询问题。 - 示例题目:POJ 2528, POJ 2828, POJ 2777, POJ 2886, POJ 2750 - **...

    经典 的POJ 分类

    根据给定的信息,我们可以将这些知识点分为几个大类别:数据...以上是对经典POJ分类的详细解析,通过这些知识点的学习,可以帮助我们更好地理解和掌握算法与数据结构的基础知识,并能够应用于实际问题的解决过程中。

    算法训练方案详解

    - **示例题目**: POJ 2187, POJ 1113 - **注意事项**: 理解凸包算法的原理和实现过程。 ### 中级算法训练 #### 一、基本算法 **1. C++标准模板库的应用** - **定义**: 使用STL提供的容器、算法和迭代器等组件...

    pku_poj_2187.rar_poj 2187_凸包问题

    标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...

    ACM训练方案

    4. 凸包:poj2187等题目锻炼处理凸包问题的能力。 中级阶段的学习增加了难度,涉及: 1. C++标准模板库的应用:poj3096和poj3007等题目。 2. 复杂模拟题:poj3393等题目提升复杂场景模拟能力。 3. 图算法扩展:差分...

    POJ 分类题目

    - poj1113 - **应用场景**:适用于图形处理、碰撞检测等领域。 #### 寒假中级 **1. C++的标准模版库应用** - **定义**:学习 STL 的各种容器和算法。 - **示例题目**: - poj3096 - poj3007 - **应用场景**:...

    凸包melkman算法cpp

    凸包melkman算法cpp实现,通过poj1113题测试

    凸包melkman算法 cpp STL deque

    poj1113 melkman算法求凸包, 使用STL

    POJ算法题目分类

    POJ 算法题目分类 POJ 算法题目分类是指分类所有 POJ 题目的算法思想和解决方案,本文将对算法分类进行详细的介绍。 一、基本算法 ...* 凸包:凸包是指解决问题的凸包算法,如 poj2187、poj1113。

    acm新手训练方案新手必备

    - **几何算法**:包括凸包、最近点对等问题。 - **计算几何**:涉及几何对象的表示与操作。 - **高级数据结构**:例如线段树、树状数组、差分约束系统等。 - **字符串算法**:包括后缀数组、AC自动机等。 - **组合...

    POJ题目简单分类(ACM)

    - **凸包**:找到包含所有点的最小凸多边形,如poj2187。 这些知识点是ACM竞赛中常见的主题,掌握了这些,可以有效提升解决算法问题的能力。对于初级选手,可以从基础算法开始,逐步挑战更复杂的图算法和数据结构...

    ACM算法总结大全——超有用!

    4. 凸包:找到一组点的最小凸包,如poj2187、poj1113。 中级阶段: 1. C++标准模板库的应用:如STL中的容器、算法等。 2. 复杂模拟题:如poj3393、poj1472等。 3. 差分约束系统、最小费用最大流、双连通分量和强...

Global site tag (gtag.js) - Google Analytics