W : Global Warming

23Dec13

I recently participated in the Advent Programming Contest 2013 organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt), wherein – as I’d recently received from Udacity a certificate for Introduction to Programming : Problem Solving with Java (CS046) – I challenged myself to program my solutions to the problems posed by the contest using only Java (I’d used C and C++ when I’d participated in the contest in 2012); I solved eighteen of the problems posed by the contest, achieving a rank of 10th (out of 155 participants).

As submissions of solutions to the contest are now closed, I’m posting here the solutions I submitted to the contest.

Problem (W; medium difficulty):

Global Warming

Remember Santa’s warehouse from problem Q?

At the North Pole, Santa has a big warehouse for storing the produced toys. The warehouse has a rectangular base area of 100 x 50 meter. All contents inside the warehouse are placed within perfect cuboid boxes. The dimensions and positions of the boxes are given.

Inside the warehouse, the elves had built a huge snowman with a solid volume of 6414 cubic meters of snow. The snow melted, probably due to Global Warming and filled the warehouse with water. Fortunately, the boxes are heavy enough not to float and waterproof. How high will the water rise inside the building? You can assume that one cubic meter of snow melts into 100 liter of water. Seepage or evaporation of water shall be neglected.

Advent Programming Contest 2013 - W

Problem

Your task is to implement a program that reads the dimensions and positions for the boxes. If two boxes are placed at overlapping coordinates, the box that was specified first is on the ground while the other one is located on top of the first one. Your programm shall first read a number indicating the number of boxes, followed by lines of 5-tuples (seperated by space) indicating the boxes x-position, y-position inside the warehouse and the width, length and height dimensions of the box. The x and y position are at the center of the box, and the box’s width is aligned to the x-direction within the warehouse. After reading all information about the boxes the water height shall be caculated in meter, rounded to two decimals after the comma. Trailing zeros shall not be printed.

Example

Input

2
40 25 25 25 5
30 30 4 4 2

Output

0.15

Solution (W.java):

import java.util.Scanner;
import java.text.DecimalFormat;

class AABB
{
  public double m_originX, m_originY, m_halfWidth, m_halfHeight, m_bottom, m_top;

  public AABB( double p_originX, double p_originY, double p_halfWidth, double p_halfHeight )
  {
    m_originX = p_originX;
    m_originY = p_originY;
    m_halfWidth = p_halfWidth;
    m_halfHeight = p_halfHeight;
  }

  public void setTopAndBottom( double p_top, double p_bottom )
  {
    m_top = p_top;
    m_bottom = p_bottom;
  }
}

public class W
{
  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    AABB boxes[] = new AABB[ s.nextInt() ];
    for( int i = 0; i < boxes.length; i ++ )
    {
      boxes[ i ] = new AABB( s.nextInt(), s.nextInt(), s.nextInt() / 2.0, s.nextInt() / 2.0 );
      final int h = s.nextInt();
      final AABB b = collision( boxes[ i ], boxes, i );
      if( b == null )
        boxes[ i ].setTopAndBottom( h, 0 );
      else
        boxes[ i ].setTopAndBottom( b.m_top + h, b.m_top );
      sortByTop( boxes, i );
    }

    double top, bottom = 0, volume = 6414 * 100 / 1000.0;
    while(( top = nextTop( boxes, bottom )) != -1 )
    {
      final AABB section = new AABB( 0, ( top - bottom ) / 2 + bottom, Integer.MAX_VALUE / 2.0, ( top - bottom ) / 2 );
      double area = 100 * 50;
      for( int i = 0; i < boxes.length; i ++ )
      {
        final AABB box = new AABB( boxes[ i ].m_originX, ( boxes[ i ].m_top - boxes[ i ].m_bottom ) / 2 + boxes[ i ].m_bottom, boxes[ i ].m_halfWidth, ( boxes[ i ].m_top - boxes[ i ].m_bottom ) / 2 );
        if( collision( section, box ))
          area -= ( boxes[ i ].m_halfWidth * 2 * boxes[ i ].m_halfHeight * 2 );
      }

      final double old_volume = volume;
      volume -= ( area * ( top - bottom ));
      if( volume <= 0 )
      {
        DecimalFormat dF = new DecimalFormat();
        dF.setDecimalSeparatorAlwaysShown( false );
        dF.setMinimumFractionDigits( 0 );
        dF.setMaximumFractionDigits( 2 );
        System.out.println( dF.format( old_volume / area + bottom ));
        break;
      }

      bottom = top;
    }
  }

  private static boolean collision( double coordinateA, double halfDimensionA, double coordinateB, double halfDimensionB )
  {
    double d = coordinateA - coordinateB;
    if( d < 0 )
      d = -d;
    d -= ( halfDimensionA + halfDimensionB );
    return d < 0;
  }

  private static AABB collision( AABB box, AABB boxes[], int limit )
  {
    for( int i = 0; i < limit; i ++ )
      if( collision( box.m_originX, box.m_halfWidth, boxes[ i ].m_originX, boxes[ i ].m_halfWidth ) && collision( box.m_originY, box.m_halfHeight, boxes[ i ].m_originY, boxes[ i ].m_halfHeight ))
        return boxes[ i ];
    return null;
  }

  private static void sortByTop( AABB boxes[], int limit )
  {
    boolean sort_occurred;
    do
    {
      sort_occurred = false;
      for( int i = 0; i < limit; i ++ )
        if( boxes[ i ].m_top < boxes[ i + 1 ].m_top )
        {
          sort_occurred = true;
          final AABB b = boxes[ i ];
          boxes[ i ] = boxes[ i + 1 ];
          boxes[ i + 1 ] = b;
        }
    }
    while( sort_occurred );
  }

  private static double nextTop( AABB boxes[], double bottom )
  {
    for( int i = boxes.length - 1; i >= 0; i -- )
      if( boxes[ i ].m_top > bottom )
        return boxes[ i ].m_top;
    return -1;
  }

  private static boolean collision( AABB a, AABB b )
  {
    return collision( a.m_originX, a.m_halfWidth, b.m_originX, b.m_halfWidth ) && collision( a.m_originY, a.m_halfHeight, b.m_originY, b.m_halfHeight );
  }
}

Testing:

2
40 25 25 25 5
30 30 4 4 2
0.15
Advertisements


No Responses Yet to “W : Global Warming”

  1. Leave a Comment

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


%d bloggers like this: