UVa: 11515 (Cranes)


1. try all possible combination to find out the maximum area

2. you don’t need to use double / float point

3. suppose there are two cranes a and b
distance_between_these_two = square_root ( (a.x – b.x) ^ 2 + (a.y – b.y) ^ 2 )
radius_sum = a.r + b.r

if ( distance_between_these_two <= radius_sum )
then, they are sharing some common spaces

4. we can simple impose square_root operation to opposite side
so we don't need any double precision number
dist = (a.x – b.x) ^ 2 + (a.y – b.y) ^ 2
rad = (a.r + b.r) ^ 2

5. there are total n cranes
loop through i = 1 to i < (1 << n)
values of 'i' will be 1 to ( 2 ^ n ) – 1
that is, all possible combination of cranes


// http://uva.onlinejudge.org/external/115/11515.html
// Runtime : 0.012s
// Tag : math, distance

//============================================================================
// Name        : UVa_11515.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

struct crane {
	int x;
	int y;
	int r;
} a [15 + 3];

int n;

int p2 (int x)
{
	return x * x;
}

bool is_conflict (int p)
{
	for ( int i = 0; i < n; i++ ) {
		if ( (1 << i) & p ) {	// i selected
			for ( int j = i + 1; j < n; j++ ) {
				if ((1 << j) & p ) {	// j selected
					int dist = p2 (a [i].x - a [j].x) + p2 (a [i].y - a [j].y);
					if ( dist <= p2 (a [i].r + a [j].r) ) return true;
				}
			}
		}
	}

	return false;
}

int calcArea (int p)
{
	int ret = 0;

	for ( int i = 0; i < n; i++ ) {
		if ( (1 << i) & p )
			ret += p2(a [i].r);
	}

	return ret;
}

int main ()
{
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {
		scanf ("%d", &n);

		for ( int i = 0; i < n; i++ )
			scanf ("%d %d %d", &a [i].x, &a [i].y, &a [i].r);

		int maxi = -1;

		for ( int i = 1; i < (1 << n); i++ ) {
			if ( !is_conflict (i))
				maxi = max (maxi, calcArea(i));
		}

		printf ("%d\n", maxi);
	}

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

One thought on “UVa: 11515 (Cranes)

  1. 
    // Waterloo site:
    // http://plg1.cs.uwaterloo.ca/~acm00/081004/data/
    
    Judge input:
    20
    7
    95 38 9
    4 60 9
    94 32 5
    93 88 15
    78 41 6
    79 69 14
    71 82 15
    6
    41 34 12
    7 75 14
    35 17 25
    37 77 5
    34 70 14
    32 95 8
    9
    72 66 1
    47 77 1
    21 57 1
    63 55 1
    16 44 1
    76 63 1
    59 72 1
    89 85 1
    15 32 1
    5
    70 60 16
    60 2 16
    89 41 18
    88 28 13
    71 59 29
    9
    10 2 12
    48 97 29
    28 31 28
    76 2 43
    41 27 30
    54 82 54
    93 55 23
    7 88 36
    88 70 5
    5
    75 56 15
    95 63 20
    49 91 23
    62 32 2
    9 52 4
    7
    92 17 16
    16 39 44
    36 5 2
    80 73 10
    98 65 21
    77 80 25
    58 58 10
    7
    93 97 22
    39 3 19
    84 45 2
    41 98 17
    43 79 18
    71 14 13
    61 77 8
    6
    36 34 33
    70 28 36
    77 25 47
    60 41 25
    64 53 18
    99 23 21
    8
    54 91 11
    44 86 2
    16 31 3
    17 26 13
    89 50 5
    77 4 1
    23 84 6
    87 13 5
    8
    19 14 1
    70 95 18
    27 20 10
    45 2 20
    67 68 10
    96 20 24
    8 32 9
    25 13 9
    8
    62 52 11
    26 89 16
    42 64 18
    99 13 16
    98 90 18
    34 57 10
    9 41 3
    14 95 5
    8
    91 1 25
    38 17 17
    54 37 21
    55 84 27
    39 34 1
    42 14 14
    0 62 8
    18 63 28
    6
    16 62 56
    15 75 47
    9 11 17
    28 90 5
    83 53 57
    11 12 6
    6
    45 17 26
    29 11 32
    95 96 8
    63 9 2
    10 84 30
    17 51 29
    5
    72 59 7
    32 45 12
    33 15 4
    41 22 2
    34 57 2
    7
    74 79 9
    86 73 24
    15 84 6
    49 98 7
    3 85 11
    98 39 9
    23 37 18
    10
    68 25 12
    8 19 53
    37 57 72
    26 40 13
    22 97 28
    27 23 41
    48 55 50
    99 85 3
    12 91 72
    54 7 41
    6
    61 25 16
    8 77 19
    95 30 8
    7 90 15
    74 84 13
    22 71 22
    10
    38 37 3
    0 88 7
    55 2 7
    21 13 7
    90 83 5
    82 68 6
    71 11 7
    8 69 8
    81 51 2
    24 17 3
    
    Judge Output:
    423
    910
    9
    1097
    3314
    949
    2817
    1371
    2209
    377
    1382
    1066
    1707
    3563
    1992
    213
    1151
    5337
    973
    334
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s