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

凸包练习: POJ 2187(JAVA)

阅读更多
分治化求凸包,请参看:http://128kj.iteye.com/admin/blogs/1748622
POJ 2187题意:
   给出一个点集,求两点之间最长的距离的平方,最长距离的两个点一定在凸包上,
首先,将点集凸包化,这样就可以排除了很多点,接下来就是两个for就可以.

下面是AC过代码:

import java.util.*;      
class Line {//线      
 Point p1, p2;      
 Line(Point p1, Point p2) {      
  this.p1 = p1;      
  this.p2 = p2;      
 }      
  public Point getP1(){
    return p1;
  }

  public Point getP2(){
    return 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 double dis(Point p1,Point p2){
     double dx = Math.abs(p1.x - p2.x);   
     double dy = Math.abs(p1.y - p2.y);   
     return (dx * dx + dy * dy);   
  }

  //计算最长距离的平方   
  private static void answer(List<Line> ls) {  
   
    List<Point> l=new ArrayList<Point>();//凸包中的所有点
   for (int i = 0; i < ls.size(); i++) {   
      Line line=ls.get(i);
      Point p1=line.getP1();
      Point p2=line.getP2();
      if(!l.contains(p1)) l.add(p1);
      if(!l.contains(p2)) l.add(p2);
   }   
   double ans=0;
    for (int i=0;i<l.size()-1;i++)
        for (int j=i+1;j<l.size();j++){
           double tem=dis(l.get(i),l.get(j));
            if (ans<tem)
                ans=tem;
        }
    System.out.printf("%.0f\n",ans);
    
  }   
  
  public static void main(String[] args) {   
    Scanner cin = new Scanner(System.in);   
    int n = 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();   
    answer(ls);
  }   
}  

0
1
分享到:
评论

相关推荐

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

    这篇博客“学习凸包(三): 凸包练习 POJ 1113”显然是关于如何通过编程解决凸包问题的一个实例。我们将深入探讨这个话题,主要关注凸包的定义、常见的求解算法以及如何用Java实现。 凸包可以被定义为一个给定集合中...

    pku_poj_2187.rar_poj 2187_凸包问题

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

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

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

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

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

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

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

    高级算法设计实验1分治算法:求解凸包问题

    求解凸包问题:输入是平面上 n 个点的集合 Q,凸包问题是要输出一个 Q 的 凸包。其中,Q 的凸包是一个凸多边形 P,Q 中的点或者在 P 上或者在 P 中。 实现基于枚举方法的凸包求解算法 实现基于 Graham-Scan 的凸包...

    poj题目分类

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

    ACM训练方案

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

    ACM 新手指南 PKU 题目分类

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

    计算几何求凸包算法的java实现

    在给定的Java程序中,“计算几何求凸包算法的java实现”是解决这个问题的关键。 这个Java代码实现了对离散点集进行求解凸包的过程。在图形用户界面中,用户可以通过鼠标点击生成点,程序会实时地计算这些点的凸包并...

    算法训练方案详解

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

    经典 的POJ 分类

    - POJ 2976:凸包构建与性质分析。 - POJ 3150、POJ 3422:复杂几何形状的计算。 以上是对经典POJ分类的详细解析,通过这些知识点的学习,可以帮助我们更好地理解和掌握算法与数据结构的基础知识,并能够应用于...

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

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

    最小凸包算法Java版

    最小凸包算法是一种在计算机科学中...总之,"最小凸包算法Java版"项目为学习和实践凸包算法提供了一个良好的起点。通过深入研究代码,我们可以不仅理解算法本身,还能掌握如何在实际项目中运用它,提升我们的编程技能。

    凸包问题Graham解决方案java实现

    java实现利用Graham算法解决凸包问题,带界面验证

    Java版凸包问题解决代码

    自己写的解决凸包问题的代码,还具备界面。

    POJ1113-Wall【凸包】

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

    凸包程序 java版

    凸包程序 java版

    Melkman凸包算法及Java实现

    **Melkman凸包算法详解** Melkman算法是一种在线算法,主要用于计算简单多边形的边界凸包。在计算机图形学、机器学习和数据结构领域,凸包问题是一个非常重要的概念,它可以帮助我们找到一组点中最外层的点集,这些...

Global site tag (gtag.js) - Google Analytics