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

POJ 1654 Area [解题报告] Java

Area

问题描述 :

You are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex. For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2.

For example, this is a legal polygon to be computed and its area is 2.5:

输入:

The first line of input is an integer t (1 <= t <= 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North, South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.

输出:

For each polygon, print its area on a single line.

样例输入:

4
5
825
6725
6244865

样例输出:

0
0
0.5
2

解题代码:

/* @author: */
import java.util.*;
public class Main {
static long get_Area(long x1,long y1, long x2,long y2)
{
        return x1*y2-x2*y1;
}

public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
int move[][]={{0,0},{1,-1},{1,0},{1,1},{0,-1},{0,0},{0,1},{-1,-1},{-1,0},{-1,1}};

    int d,ncase;
    long x0,y0,newx,newy,area; 
    ncase=sc.nextInt();
    String  ss;
    while((ncase--)!=0)
    {
       ss=sc.next();
       
        x0=y0=area=0;
        for(int i=0;i<=ss.length()-1;i++)
        {
            d=ss.charAt(i)-'0';
            newx=x0+move[d][0];
            newy=y0+move[d][1];
            area+=get_Area(x0,y0,newx,newy);      
            x0=newx;
            y0=newy;
        }
        if(area< 0)
           area*=-1;
        if(area%2!=0)
           System.out.printf("%d.5\n",area/2);
        else
           System.out.printf("%d\n",area/2); 
    }
   }
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  4. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥