文档章节

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

一贱书生
 一贱书生
发布于 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
私信 提问
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
人工智障学习笔记——深度学习(1)神经网络

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

sm9sun
2017/12/26
0
0
题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】

题面 农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。 他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。 我们假定,他的农场划分成 N x N 的方格。输入数据...

Chicago_01
11/07
0
0
校招FLAG&BATJ&TMD等大厂笔试面试备考第271道286道题目

第271道选H 解析:看分针转动的角度。 第272道选D 奇数项90度顺时钟旋转成规律 第273道选4 解析:看外框内有几条直线 第一套图都是:2条直线 第二套图都是:5条直线 第274道选D 解析:两套图...

天善智能
07/31
0
0
分类算法之邻近算法:KNN(理论篇)

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

weapon
2017/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

开源软件会被云杀死吗 ?

本文转载云头条,原作者:Michael Stiefel是Reliable Software公司的负责人,是一名软件架构和开发顾问。 文章要点 虽然开源开发不会消失,但商业开源厂商的未来不是很有希望。随着全面管理的...

linuxCool
36分钟前
2
0
OSChina 周三乱弹 —— 谈什么对象?睡什么觉?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @胖达panda :最肯忘却古人诗,最不屑一顾是相思。分享童丽的单曲《红豆生南国》: 《红豆生南国》- 童丽 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
40分钟前
185
5
stylus

stylus基础教程,stylus实例教程,stylus语法总结

miaojiangmin
今天
5
0
PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
今天
2
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部