文档章节

在二维平面上,有两个正方形,请找出一条直线,能够将这两个正方形对半分

一贱书生
 一贱书生
发布于 2016/11/19 11:10
字数 1036
阅读 22
收藏 0

/**
 * 功能:在二维平面上,有两个正方形,请找出一条直线,能够将这两个正方形对半分。
 * 假定正方形的上下两条边与x轴平行。

 */

 

[java] view plain copy

 

  1. /** 
  2.  * 考虑: 
  3.  * 线的准确含义,可能性有: 
  4.  *      1)由斜率和y轴截距确定; 
  5.  *      2)由这条边上的任意两点确定; 
  6.  *      3)线段,以正方形的边作为起点和终点。 
  7.  *  
  8.  * 假设:这条线的端点应该落在正方形的边上。 
  9.  * 思路:要将两个正方形对半分,这条线必须连接两个正方形的中心点。 
  10.  */  
  11.   
  12. public class Square {  
  13.   
  14.     //正方形的四条边  
  15.     int left;  
  16.     int right;  
  17.     int top;  
  18.     int bottem;  
  19.     int size;  
  20.       
  21.     public static void main(String[] args) {  
  22.         // TODO Auto-generated method stub  
  23.   
  24.     }  
  25.   
  26.     //得到正方形的中心点的位置  
  27.     public Point getMiddle(){  
  28.         return new Point((this.left+this.right)/2.0,(this.top+this.bottem)/2);  
  29.     }  
  30.       
  31.     //返回线段mid1和mid2的线段与square2的边相交的点,即从mid1到mid2画一条线,一直延伸置碰到square2的靠外的那条边。  
  32.     public Point extend(Point mid1,Point mid2,int size){  
  33.         //确定线段mid1->mid2的方向  
  34.         int xdir=mid1.x<mid2.x?1:-1;  
  35.         int ydir=mid1.y<mid2.y?1:-1;  
  36.           
  37.         //如果mid1和mid2的x坐标相同,计算斜率时,会抛出零异常,做特别处理  
  38.         if(mid1.x==mid2.y)  
  39.             return new Point(mid2.x,mid2.y+ydir*size/2.0);  
  40.           
  41.         //计算线段的斜率  
  42.         double slope=(mid2.y-mid1.y)/(mid2.x-mid1.x);  
  43.         double x1=0;  
  44.         double y1=0;  
  45.           
  46.         //计算相交点,注意斜率的取值  
  47.         if(Math.abs(slope)==1){  
  48.             x1=mid2.x+xdir*size/2.0;  
  49.             y1=mid2.y+ydir*size/2.0;  
  50.         }else if(Math.abs(slope)<1){  
  51.             x1=mid2.x+xdir*size/2.0;  
  52.             y1=mid2.y+slope*ydir*(size/2.0);//注意方向  
  53.         }else if(Math.abs(slope)>1){  
  54.             x1=mid2.x+slope*xdir*(size/2.0);  
  55.             y1=mid2.y+ydir*size/2.0;  
  56.         }  
  57.         return new Point(x1,y1);  
  58.     }  
  59.       
  60.     public MyLine cut(Square other){  
  61.         //计算两个中心点之间的线段与正方形的边相交的位置  
  62.         Point point1=extend(this.getMiddle(),other.getMiddle(),other.size);  
  63.         Point point2=extend(this.getMiddle(),other.getMiddle(),-other.size);  
  64.         Point point3=extend(other.getMiddle(),this.getMiddle(),this.size);  
  65.         Point point4=extend(other.getMiddle(),this.getMiddle(),-this.size);  
  66.           
  67.         //找出线段的起点和终点  
  68.         Point start=point1;  
  69.         Point end=point1;  
  70.         Point[] points={point1,point2,point3};  
  71.         for(int i=0;i<points.length;i++){  
  72.             if(points[i].x<start.x||points[i].x==start.x&&points[i].y<start.y)  
  73.                 start=points[i];  
  74.             else if(points[i].x>end.x||points[i].x==end.x&&points[i].y>end.y)  
  75.                 end=points[i];  
  76.         }  
  77.           
  78.         return new MyLine(start,end);  
  79.     }  
  80.       
  81. }  
  82.   
  83. class MyLine{  
  84.     Point start;  
  85.     Point end;  
  86.     public MyLine(Point start,Point end){  
  87.         this.start=start;  
  88.         this.end=end;  
  89.     }  
  90. }  
  91.   
  92. class Point{  
  93.     double x;  
  94.     double y;  
  95.     public Point(double x,double y){  
  96.         this.x=x;  
  97.         this.y=y;  
  98.     }  
  99. }

或者:

public static double[] getBipartition(Point[] A, Point[] B) {                                                    

    // 此题由于正方形的上下两条边与x轴平行, 所以就不用直线相交去求中心点了                           

    // 求出第一个点不同的坐标(因为点的顺序可能是混乱的)                                     

    double p1x1 = A[0].x;                                            

    double p1x2 = A[1].x == A[0].x ? A[2].x:A[1].x;                  

    double p1y1 = A[0].y;                                            

    double p1y2 = A[1].y == A[0].y ? A[2].y:A[1].y;                  

                                                                       

    // 求出第二个点不同的坐标(因为点的顺序可能是混乱的)                                     

    double p2x1 = B[0].x;                                            

    double p2x2 = B[1].x == B[0].x ? B[2].x:B[1].x;                  

    double p2y1 = B[0].y;                                            

    double p2y2 = B[1].y == B[0].y ? B[2].y:B[1].y;                  

                                                                       

    // 平分线的两个点                                                       

    double x1 = (double)(p1x2 + p1x1) / 2;                           

    double y1 = (double)(p1y2 + p1y1) / 2;                           

    double x2 = (double)(p2x1 + p2x2) / 2;                           

    double y2 = (double)(p2y1 + p2y2) / 2;                           

                                                                       

    double k = (double)(y2 - y1) / (x2 - x1);                        

    double b = y1 - k*x1;                                            

                                                                       

    return new double[] {k,b};                                       

}  

 

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

public class Bipartition {

    public double[] getBipartition(Point[] A, Point[] B) {

        // write code here

        //平分直线必定经过正方形的中心点

        int x1 = (A[0].x+A[2].x)/2;

        int y1 = (A[0].y+A[2].y)/2;

         

        int x2 = (B[0].x+B[2].x)/2;

        int y2 = (B[0].y+B[2].y)/2;

         

        double[] a = new double[2];

        a[0]=(double)(y2-y1)/(double)(x2-x1);

        a[1]=y2-a[0]*x2;

        return a;

    }

}

 

public class Bipartition {

    public double[] getBipartition(Point[] A, Point[] B) {

        // write code here

        double Acenterx=0;//正方形A的中心x坐标

        double Acentery=0;//正方形A的中心y坐标

        

        for(int i=0;i<4;i++){

            Acenterx+=A[i].x;

            Acentery+=A[i].y;

        }

        Acenterx/=4.0;

        Acentery/=4.0;

        

        double Bcenterx=0;//正方形B的中心x坐标

        double Bcentery=0;//正方形B的中心y坐标

        for(int i=0;i<4;i++){

            Bcenterx+=B[i].x;

            Bcentery+=B[i].y;

        }

        Bcenterx/=4.0;

        Bcentery/=4.0;

        

        double[] result=new double[2];

        result[0]=(Bcentery-Acentery)/(Bcenterx-Acenterx);//求斜率

        result[1]=Acentery-result[0]*Acenterx;//求截距

        

        return result;

    }

}

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
人工智障学习笔记——深度学习(1)神经网络

一.神经网络 我们所说的深度学习,其最基础最底层的模型称之为"神经网络"(neural network),因为我们希望机器能够像我们人类大脑的神经网络处理事件一样去解决问题,最终达到"人工智能"的效...

sm9sun
2017/12/26
0
0
Path 常用方法解析

1. 概述 The Path class encapsulates compound (multiple contour) geometric paths consisting of straight line segments, quadratic curves, and cubic curves. It can be drawn with c......

ForeverCy
2017/08/01
0
0
分类算法之邻近算法:KNN(理论篇)

起步 今天介绍另一种分类算法,k邻近算法( ),即 KNN 算法。 概述 Cover 和 Hart 在 1968 年提出了最初的邻近算法,用于解决分类( )的问题。关于这个算法在维基百科中也有介绍:https://zh.w...

weapon
2017/12/06
0
0
台湾大学林轩田机器学习基石课程学习笔记5 -- Training versus Testing

上节课,我们主要介绍了机器学习的可行性。首先,由NFL定理可知,机器学习貌似是不可行的。但是,随后引入了统计学知识,如果样本数据足够大,且hypothesis个数有限,那么机器学习一般就是可...

红色de石头
2017/07/11
0
0
LOD层次细节算法-大规模实时地形的绘制

背景 在介绍层次细节算法之前,先来看两幅图片。 图一 图二 这两幅图片是用层次细节算法也即LOD算法绘制的地形网格。为了更清晰的看清地形网格的结构,我没有给其贴上纹理。这两幅图片看上去...

乐观的vc
2013/04/14
0
6

没有更多内容

加载失败,请刷新页面

加载更多

GO冒泡,二分查找

package mainimport("fmt")func main() {var arr [5]int = [5]int{11,13,9,2,25}maopao(&arr)fmt.Println("arr = ", arr) //[2 9 11 13 25]findIndex := binaryFind(&arr, 0......

汤汤圆圆
15分钟前
1
0
工作2年半跳槽面试阿里,成功拿到offer,凭什么?

2015年刚毕业的我,进入了一家小小的公司实习工作,在学校学了三年软件开发的我,还是想去寻找一份互联网行业的工作,这样更能学以致用发挥自己的特长。一直到18年三月份,我辞掉已有的工作,...

java知识分子
20分钟前
1
0
讲述下:Linux的10个最危险的命令

导读 Linux命令行佷有用、很高效,也很有趣,但有时候也很危险,尤其是在你不确定你自己在正在做什么时候。这篇文章将会向你介绍十条命令,但你最好不要尝试着去使用。 当然,以下命令通常都...

问题终结者
24分钟前
1
0
分库分表后如何部署上线?

引言 我们先来讲一个段子 面试官:“有并发的经验没?” 应聘者:“有一点。” 面试官:“那你们为了处理并发,做了哪些优化?” 应聘者:“前后端分离啊,限流啊,分库分表啊。。” 面试官:...

Java烂猪皮
29分钟前
1
0
Redis源码阅读笔记-快速列表

快速列表 快速列表(quicklist)是由压缩列表(ziplist)组成的一个双向链表,链表中,每一个节点都是以压缩列表(ziplist)的结构保存。 在 Redis3.2 后加入的新数据结构,在列表键中取代了双向链...

Jian_Ming
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部