首页 > 专题系列 > Java解POJ > POJ 3198 Polygon Encoder [解题报告] Java
2013
11-12

POJ 3198 Polygon Encoder [解题报告] Java

Polygon Encoder

问题描述 :

Imagine an infinite table with rows and columns numbered using the natural numbers. The following figure shows a procedure to traverse such a table assigning a consecutive natural number to each table cell:

This enumeration of cells can be used to represent complex data types using natural numbers:

  • A pair of natural numbers (i, j) is represented by the number corresponding to the cell in row i and column j. For instance, the pair (3, 2) is represented by the natural number 17; this fact is noted by P2(3, 2) = 17.

  • The pair representation can be used to represent n-tuples. A triplet (a, b, c) is represented by P2(a, P2(b, c)). A 4-tuple (a, b, c, d) is represented by P2(a, P2(b, P2(c, d))). This procedure can be generalized for an arbitrary n:

    Pn(a1, …, an) = P2(a1, Pn−1(a2, …, an)),

    where Pn denotes the n-tuple representation function, n ≥ 2. For example P3(2, 0, 1) = 12.

  • A list of arbitrary length ‹a1, …, an› is represented by

    L(‹a1, …, an›) = P2(n, Pn(a1, …, an)).

    For example, L(‹0, 1›) = 12.

The Association of Convex Makers (ACM) uses this clever enumeration scheme in a polygon representation system. The system can represent a polygon, defined by integer coordinates, using a natural number as follows: given a polygon defined by a vertex sequence ‹(x1, y1), …, (xn, yn)› assign the natural number:

L(‹P2(x1, y1), …, P2(xn, yn)›).

ACM needs a program that, given a natural numbers that represents a polygon, calculates the area of the polygon. It is guaranteed that the given polygon is a simple one, i.e. its sides do not intersect.

As an example of the problem, the triangle with vertices at (1,1), (2,0) and (0,0) is codified with the number 2141. The area of this triangle is 1.

输入:

The input consists of several test cases. Each test case is given in a single line of the input by a natural number representing a polygon. The end of the test cases is indicated with *.

输出:

One line per test case, preserving the input order. Each output line contains a decimal number telling the area of the corresponding encoded polygon. Areas must be printed with 1 decimal place, truncating less significative decimal places.

样例输入:

2141
206
157895330
*

样例输出:

1.0
0.5
1.0

解题代码:

/* @author: */
import java.math.BigInteger;
import java.util.*;


public class Main
{
    public static BigInteger get( BigInteger h ) {
        BigInteger s = h.shiftLeft(1);
        BigInteger a = BigInteger.ONE.shiftLeft( s.bitLength()/2-1 ).subtract( BigInteger.ONE );
        BigInteger b = BigInteger.ONE.shiftLeft( s.bitLength()/2+1 ), c;
        
        while( a.add(BigInteger.ONE).compareTo(b) < 0 ) {
            c = a.add( b ).shiftRight(1);
            if( c.multiply( c.add(BigInteger.ONE)).compareTo( s ) <=0 )
                a = c;
            else
                b = c;
        }

        return a;
    }
    public static BigInteger X, Y;
    public static void Get( BigInteger s ) {
        BigInteger t = get( s );
        Y = s.subtract( t.multiply(t.add(BigInteger.ONE)).shiftRight(1) );
        X = t.subtract( Y );
    }
    
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        String s;
        while( true ) {
            s = cin.next();
            if( s.equals( "*" ) )
                break;
            BigInteger a = new BigInteger( s ), t = BigInteger.ONE, h = BigInteger.ONE, sum = BigInteger.ZERO, 
                x =BigInteger.ONE, 
                y=BigInteger.ONE, xt=BigInteger.ONE, yt=BigInteger.ONE, x0 = BigInteger.ONE, y0=BigInteger.ONE;
            Get( a );
            t = X; h = Y;
            //System.out.println( X+","+Y );
            //if(X==t)continue;
            int n = t.intValue();
            
            for( int i=0; i< n; i++ ) {
                a = h;
                if( i < n-1 ) {
                    Get( a );
                    t = X; h = Y;
                }
                else
                    t = a;
                
                Get( t );
                x = X; y = Y;
                if( i == 0 ) {
                    x0 = x; y0 = y;
                }
                else {
                    sum = sum.add( x.multiply(yt).subtract( y.multiply(xt) ));
                }
                xt = x; yt = y;
                //System.out.println( x + "," + y );
            }
            sum = sum.add( x0.multiply(yt).subtract( y0.multiply(xt) ));
            sum = sum.abs();
            
            System.out.print( sum.shiftRight(1) );
            if( sum.equals(sum.shiftRight(1).shiftLeft(1)))
                System.out.println( ".0" );
            else
                System.out.println( ".5");
        }
        return;
    }

}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks