Poj Solution 1948

http://poj.org/problem?id=1948

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <list>
using namespace std;
bool sign[800][800];
int l[40], n;
typedef pair<int,int> node;
node q[800*800];
int qn;
int main()
{
    int i, j, x, y, s, m;
    list< node >::iterator iter;

    scanf( "%d", &n );
    
    for( s=0,i=0; i<n; i++ )
    {
        scanf( "%d", l+i );
        s += l[i];
    }
    memset( sign, 0, sizeof( sign ) );
    sign[0][0] = 1;    
    qn = 1;
    q[0].first = 0;
    q[0].second = 0;
    for( i=0; i<n; i++ )
    {
        for( j = 0,m = qn; j < m; j++ )
        {
            x = q[j].first;
            y = q[j].second;
            if( x + l[i] <= s/2  && !sign[ x+l[i] ][y] )
            {
                sign[x+l[i]][y] = sign[y][x+l[i]] = true;
                q[qn].first = x+l[i];
                q[qn].second = y;
                qn++;
            }
            if( y + l[i] <= s/2 && !sign[ y+l[i] ][x] )
            {
                sign[y+l[i]][x] = sign[x][y+l[i]] = true;
                q[qn].first = y+l[i];
                q[qn].second = x;
                qn++;
            }
        }
    }
    double ans = -1, p, temp;
    for( i=0; i <= s/2; i++ )
    for( j=i; j <= s/2; j++ )
    if( sign[i][j] && j+i > s-(j+i) && j-i < s-(j+i) && s-j > j )
    {

        p = (double)s/2;
        if( ( temp=sqrt( p*(p-j)*(p-i)*(p-(s-i-j)) ) ) > ans )
            ans = temp;
    }
    if( ans == -1 )printf( "-1n" );
    else printf( "%dn", (int)(ans*100) );    
    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *