首页 > 搜索 > BFS搜索 > POJ 2172 Bricks [解题报告] Java
2013
11-10

POJ 2172 Bricks [解题报告] Java

Bricks

问题描述 :

The prisoner of the “IF” castle has decided to run away by disassembling the brick wall in his prison cell. To hide his work from his jailors he shall get rid of the bricks that he removes from the wall. All bricks have a shape of rectangular parallelepiped with the size of A * B * C inches and are so strong that they are impossible to break. However, there’s a small rectangular sewer hole in the cell’s floor with the size of D * E inches that goes deep down as a rectangular well of the same size (so deep it is, that its depth could not be measured and can be neglected). The prisoner have precisely (up to a tenth of an inch!) measured all the sizes A, B, C, D, E and wants to know if it is possible to dispose of the castle’s bricks through the hole in the floor. Please, answer this question for him.

输入:

The input consists of a single line with 5 numbers A, B, C, D, and E separated by spaces. A, B, C are the lengths of brick’s sides, and D, E are the lengths of hole’s sides. All lengths are at least 1 and at most 10 inches and have at most 1 digit after decimal point.

输出:

Write to the output a single word YES if it is possible to dispose of the bricks through the hole or NO otherwise.

样例输入:

1.0 2.0 1.5 1.5 1.0

样例输出:

YES

解题代码:

/* @author: */
import java.util.Scanner;
public class Main {
 static final double EPS =1e-7;
 
  //矩形x*y 能否放入 a*b 中
static  boolean canfit( double a, double b, double x, double y )
{
   double t;
   double l=Math.sqrt(x*x+y*y),ll=x*x+y*y;
   if(x*x+y*y - a*a-b*b > EPS)
	return false;
	
   if(x< y)
    {
	t=x;x=y;y=t;
    }
   if(a< b)
   {
	t=a;a=b;b=t;
   }
   if( x-b >EPS && y -b > EPS )return false;
    double s=(4*x*y*b+Math.sqrt(16*x*x*y*y*b*b-4*ll*(4*x*x*y*y-ll*ll+b*b*ll) ) )/ll/2;

   if(s-a > EPS)
	return false;
   else return true;
}

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
	
    double a, b, c, d, e;
    a=sc.nextDouble();
    b=sc.nextDouble();
    c=sc.nextDouble();
    d=sc.nextDouble();
    e=sc.nextDouble();

    if( canfit( d, e, a, b ) || canfit( d, e, a, c ) || canfit( d, e, b, c ) )
	System.out.printf( "YES\n" );
    else
	System.out.printf( "NO\n" );
	
  }
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。