首页 > ACM题库 > POJ 1408 Fishnet [解题报告] Java
2013
11-09

POJ 1408 Fishnet [解题报告] Java

Fishnet

问题描述 :

A fisherman named Etadokah awoke in a very small island. He could see calm, beautiful and blue sea around the island. The previous night he had encountered a terrible storm and had reached this uninhabited island. Some wrecks of his ship were spread around him. He found a square wood-frame and a long thread among the wrecks. He had to survive in this island until someone came and saved him.

In order to catch fish, he began to make a kind of fishnet by cutting the long thread into short threads and fixing them at pegs on the square wood-frame. He wanted to know the sizes of the meshes of the fishnet to see whether he could catch small fish as well as large ones.

The wood frame is perfectly square with four thin edges on meter long: a bottom edge, a top edge, a left edge, and a right edge. There are n pegs on each edge, and thus there are 4n pegs in total. The positions of pegs are represented by their (x,y)-coordinates. Those of an example case with n=2 are depicted in figures below. The position of the ith peg on the bottom edge is represented by (ai,0). That on the top edge, on the left edge and on the right edge are represented by (bi,1), (0,ci) and (1,di), respectively. The long thread is cut into 2n threads with appropriate lengths. The threads are strained between (ai,0) and (bi,1),and between (0,ci) and (1,di) (i=1,…,n).

You should write a program that reports the size of the largest mesh among the (n+1)2 meshes of the fishnet made by fixing the threads at the pegs. You may assume that the thread he found is long enough to make the fishnet and the wood-frame is thin enough for neglecting its thickness.

输入:

The input consists of multiple sub-problems followed by a line containing a zero that indicates the end of input. Each sub-problem is given in the following format.

n

a1 a2 … an

b1 b2 … bn

c1 c2 … cn

d1 d2 … dn

you may assume 0 < n <= 30, 0 < ai,bi,ci,di < 1

输出:

For each sub-problem, the size of the largest mesh should be printed followed by a new line. Each value should be represented by 6 digits after the decimal point, and it may not have an error greater than 0.000001.

样例输入:

2
0.2000000 0.6000000
0.3000000 0.8000000
0.1000000 0.5000000
0.5000000 0.6000000
2
0.3333330 0.6666670
0.3333330 0.6666670
0.3333330 0.6666670
0.3333330 0.6666670
4
0.2000000 0.4000000 0.6000000 0.8000000
0.1000000 0.5000000 0.6000000 0.9000000
0.2000000 0.4000000 0.6000000 0.8000000
0.1000000 0.5000000 0.6000000 0.9000000
2
0.5138701 0.9476283
0.1717362 0.1757412
0.3086521 0.7022313
0.2264312 0.5345343
1
0.4000000
0.6000000
0.3000000
0.5000000
0

样例输出:

0.215657
0.111112
0.078923
0.279223
0.348958

解题代码:

/* @author:[email protected] */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
  static double[][][] mesh=new double[32][32][2];
  public static void main(String[] args) throws Exception{
	BufferedReader br = new BufferedReader(new
                InputStreamReader(System.in));
   String s;
   String[] ss;
   int n,i,j;
   double max=0d,t;
   while((s=br.readLine())!=null&&!"0".equals(s)){
      	n=parseInt(s);
      	s=br.readLine();
      	ss=s.split(" ",n);
      	for(i=1;i<=n;i++){
      		mesh[n+1][i][0] = Double.parseDouble(ss[i-1]);
      	}
      	s=br.readLine();
      	ss=s.split(" ",n);
      	for(i=1;i<=n;i++){
      		mesh[0][i][0] = Double.parseDouble(ss[i-1]);
      		mesh[0][i][1] = 1d;
      	}
      	s=br.readLine();
      	ss=s.split(" ",n);
      	for(i=0;i< n;i++){
      		mesh[n-i][0][1] = Double.parseDouble(ss[i]);
      	}
      	s=br.readLine();
      	ss=s.split(" ",n);
      	for(i=0;i< n;i++){
    		mesh[n-i][n+1][0] = 1d;
      		mesh[n-i][n+1][1] = Double.parseDouble(ss[i]);
      	}
      	mesh[0][0][1]=
      	mesh[0][n+1][0]=mesh[0][n+1][1]=
      	mesh[n+1][n+1][0]=1d;
        	
      	for(i=1;i<=n;i++){
         for(j=1;j<=n;j++){
      	    setPoint(mesh[n+1][j][0],mesh[0][j][0],mesh[i][0][1],mesh[i][n+1][1],i,j);
         }
      }
      	for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
          t=getSquare(mesh[i][j],mesh[i][j+1],mesh[i+1][j+1],mesh[i+1][j]);
          if(t>max)
        	max=t;
        }
       }
       System.out.printf("%.6f\n",max);
       max=0d;
       reset(n+2);
    }
   }

   static void print(int n) {
	for(int i=0;i< n;i++){
        for(int j=0;j< n;j++){
	   System.out.print("["+mesh[i][j][0]+","+mesh[i][j][1]+"]");
	  }
	 System.out.println();
	}
    }

   static void setPoint(double a,double b,double c,double d,int x,int y){
	double t=1-(a-b)*(c-d);
	mesh[x][y][0]=(a-(a-b)*c)/t;
	mesh[x][y][1]=(c-a*(c-d))/t;
   }

   static double getSquare(double[] a,double[] b,double[] c,double[] d){
	double t=Math.abs((a[0]-b[0])*(c[1]-b[1])-(a[1]-b[1])*(c[0]-b[0]));
	t+=Math.abs((a[0]-d[0])*(c[1]-d[1])-(a[1]-d[1])*(c[0]-d[0]));
	return t/2;
   }

   static void reset(int limit){
	for(int i=0;i< limit;i++){
         for(int j=0;j< limit;j++){
	   mesh[i][j][0]=mesh[i][j][1]=0d;
	  }
	}
    }

  static int parseInt(String s){
    int t = 0;
   for(char ch: s.toCharArray()){
      t *= 10;
     t += ch-'0';
  }
  return t;
 }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了