首页 > 专题系列 > Java解POJ > POJ 1687 Buggy Sat [解题报告] Java
2013
11-10

POJ 1687 Buggy Sat [解题报告] Java

Buggy Sat

问题描述 :

Discovery Co. ltd. builds a satellite using a new kind of an intelligent camera. The camera has special software to detect cities and roads from an image, and is also able to detect every region (which is a connected part of surface), bounded by a series of connected roads with no other region inside. Using this technology, the satellite is able to compress the picture before sending it. The compressed format of a picture is the city locations and its regions.

Discovery has launched the satellite, without testing the software completely. So, after a while, they received some buggy pictures which includes one more extra region: the outer region. The outer region is the region of the plane enclosing every other region (which has infinite area). Further analysis shows that all http://poj.org/images sent have the following properties:

1.All cities, in the image, have at least two roads to the other cities.

2.There is a path connecting every pair of cities.

3.There is at most one road between each pair of cities.

4.Roads do not cross each other except at the cities.



The above Figure shows a sample image received (see sample input).

You are to write a program to read a buggy image and report the outer region.

输入:

The first line of the input consists of a single integer N (1 <= N <= 20), which is the number of test cases. The test cases appear with no blank lines in between. The first line of each test case consists of the number of cities (between 1 and 50) followed by pairs of integers (x, y) which are location of cities (each pair in one line), followed by number of faces in a separate line (between 1 and 50), followed by face information on each line. Face information consists of number of cities making the face and the city numbers in clockwise (or counterclockwise) order.

输出:

There should be a single line containing the boundary face number for each test case, with no blank lines in between.

样例输入:

1
5
2 6
4 4
4 7
8 6
4 10
3
4 1 2 4 3
4 1 3 4 5
4 1 2 4 5

样例输出:

3

解题代码:

//* @author: 
import java.util.*;
class Point{
  int x;
  int y;
  public Point(){
    this.x=0;
    this.y=0;
  }

  public Point(int x,int y){
    this.x=x;
    this.y=y;
  }
}

public class Main{
 
 static int cross_product(Point a,Point b){
   return a.x*b.y-a.y*b.x;
 }

 public static void main(String args[]){
   Point p[]=new Point[55];
   Scanner in=new Scanner(System.in);
    int cse=in.nextInt();
    while(!((cse--)==0)){
       
       int pre=0;
       int tmp=0;
       int id=0;
        int n=in.nextInt();
        for(int i=0;i< n;i++){
          p[i]=new Point();
          p[i].x=in.nextInt();
          p[i].y=in.nextInt();
        }
        int x=in.nextInt();
        int maxs=-1;int ans=0;
        for(int i=0;i< x;i++){
            int y=in.nextInt();
            int sum=0;
            for(int j=0;j< y;j++){
                 id=in.nextInt();
                id--;
                if(j==0){
                    pre=id;
                    tmp=id;
                }
                else{
                    sum+=cross_product(p[pre],p[id]);
                    pre=id;
                }
            }
            sum+=cross_product(p[id],p[tmp]);
            if(sum>maxs){
                maxs=sum;
                ans=i+1;
            }
        }
        System.out.printf("%d\n",ans);
    }
   }
}

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