首页 > 搜索 > BFS搜索 > POJ 2660 War on Weather [解题报告] Java
2013
11-11

POJ 2660 War on Weather [解题报告] Java

War on Weather

问题描述 :

After an unprovoked hurricane attack on the south shore, Glorious Warrior has declared war on weather. The first salvo in this campaign will be a coordinated pre-emptive attack on as many tropical depressions as possible. GW reckons that the attack will neutralize the tropical depressions before they become storms, and dissuade others from forming.

GW has at his disposal k space-to-earth killer satellites at various locations in space. m tropical depressions are known to exist at various locations on the earth’s surface. Each satellite can attack any number of targets on the earth provided there is line of sight between the satellite and each target. How many different targets can be hit?

输入:

The input consists of several test cases. Each case begins with a line containing integers 0 < k, m <= 100 as defined above. k lines follow, each giving x,y,z - the location in space of a satellite at the scheduled time of attack. m lines then follow, each giving x,y,z - the location of a target tropical depression. Assume the earth is a sphere centred at (0,0,0) with circumference 40,000 km. All targets will be on the surface of the earth (within 10-9 km) and all satellites will be at least 50 km above the surface. A line containing 0 0 follows the last test case.

输出:

For each test case, output a line giving the total number of targets that can be hit. If a particular target falls within 10-8 km of the boundary between being within line-of-sight and not, it may be counted either way. (That is, you need not consider rounding error so long as it does not exceed 10-8 km.)

样例输入:

3 2
-10.82404031 -1594.10929753 -6239.77925152
692.58497298 -5291.64700245 4116.92402298
3006.49210582 2844.61925179 5274.03201053
2151.03635167 2255.29684503 5551.13972186
-1000.08700886 -4770.25497971 4095.48127333
3 4
0 0 6466.197723676
0 6466.197723676 0
6466.197723676 0 0
6366.197723676 0 0
6365.197723676 112.833485488 0
0 0 6366.197723676
0 -6366.197723676 0
0 0

样例输出:

2
3

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{

static double lfabs(double x)
{
    return x>0?x:-x;
}    

 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  double sat[][]=new double[100][3];
  double xa,xb,ya,yb,za,zb,s,s1,s2,s3,angle,r=20000/3.14159265;
  int k,m,i,j,flag=0,num;
    while(sc.hasNext())
    {
       k=sc.nextInt();
       m=sc.nextInt();
       if(k==0&&m==0) break;
        num=0;
        for(i=0;i< k;i++){
          sat[i][0]=sc.nextDouble();
          sat[i][1]=sc.nextDouble();
          sat[i][2]=sc.nextDouble();
        }
        for(i=0;i< m;i++)
        {
            flag=0;
            xb=sc.nextDouble();
            yb=sc.nextDouble();
            zb=sc.nextDouble();
            for(j=0;j< k;j++)
            {
                xa=sat[j][0];ya=sat[j][1];za=sat[j][2];
                s1=Math.sqrt(xa*xa+ya*ya+za*za);
                s2=Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
                if(s2<=Math.sqrt(s1*s1-r*r)){flag=1;break;}
            }    
            if(flag!=0)num++;
        }    
        System.out.printf("%d\n",num);
    }    
  }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。