-
-
Save anonymous/5fe120d31ab3765e6b04 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* rect-area.php | |
* | |
* @author Robert Bredlau | |
* @version $HeadURL$ | |
*/ | |
class proggy { | |
/** | |
* Number of rects | |
* | |
* @var int | |
*/ | |
protected $m_num = 0; | |
/** | |
* Array of existing rect objects that do not collide with each other. | |
* | |
* @var rect[] | |
*/ | |
protected $m_rects = array(); | |
/** | |
* The total area | |
* | |
* @var double | |
*/ | |
protected $m_area = 0; | |
/** | |
* @return proggy | |
*/ | |
public function __construct() { | |
} | |
public function __destruct() {} | |
protected function init() { | |
$this->m_num = 0; | |
$this->m_rects = array(); | |
$this->m_area = 0; | |
} | |
protected function execute_normal( $first_line ) { | |
$this->init(); | |
$this->m_num = $first_line; | |
for( $n = 0; $n < $this->m_num; $n += 1 ) { | |
if( $this->m_validate ) { | |
list( $n1, $n2, $n3, $n4, $new_area ) = explode( ' ', trim( fgets( STDIN ) ) ); | |
} else { | |
list( $n1, $n2, $n3, $n4 ) = explode( ' ', trim( fgets( STDIN ) ) ); | |
} | |
$incoming = array( new rect( (double)$n1, (double)$n2, (double)$n3, (double)$n4 ) ); | |
foreach( $this->m_rects as $k_exist => /** @var rect */ $existing ) { | |
$catcher = array(); | |
while( ! empty( $incoming ) ) { | |
/** @var rect */ | |
$other = array_shift( $incoming ); | |
$divisions = $existing->split( $other ); | |
if( $divisions === false ) { | |
// no collision, non intersecting | |
$catcher[] = $other; | |
} else if( empty( $divisions ) ) { | |
// fits entirely inside, so we throw it away | |
} else { | |
// intersection removed, $divisions is now N new rectangles to test | |
$incoming = array_merge( $incoming, $divisions ); | |
} | |
} | |
$incoming = $catcher; | |
} | |
foreach( $incoming as /** @var rect */ $other ) { | |
$this->m_area += $area = $other->area(); | |
if( $area !== 0 ) { | |
$this->m_rects[] = $other; | |
} | |
} | |
} | |
echo $this->m_area . PHP_EOL; | |
return $this->m_area; | |
} | |
public function execute() { | |
$start_tm = microtime( true ); | |
$last_area = 0; | |
while( true ) { | |
$matches = array(); | |
$first_line = trim( fgets( STDIN ) ); | |
if( is_numeric( $first_line ) ) { | |
$last_area = $this->execute_normal( (int)$first_line ); | |
} else if( preg_match( '/^[#](?P<expected>[0-9.]+)$/i', $first_line, $matches ) ) { | |
if( ((double)$last_area) !== ((double)$matches[ 'expected' ]) ) { | |
echo 'mismatch - ' . $last_area . ' versus expected ' . $matches[ 'expected' ] . PHP_EOL; | |
} | |
} else if( preg_match( '/^##$/i', $first_line, $matches ) ) { | |
break; | |
} else if( $first_line === 'a' ) { | |
$this->m_validate = true; | |
} | |
} | |
echo 'done in ' . number_format( microtime( true ) - $start_tm, 2 ) . ' s' . PHP_EOL; | |
} | |
} | |
class point { | |
public $x = 0; | |
public $y = 0; | |
public function x_delta( point $other ) { | |
return abs( $other->x - $this->x ); | |
} | |
public function y_delta( point $other ) { | |
return abs( $other->y - $this->y ); | |
} | |
public function __toString() { | |
return "({$this->x}, {$this->y})"; | |
} | |
} | |
class rect { | |
CONST CORNER_TL = 1; | |
CONST CORNER_TR = 2; | |
CONST CORNER_BL = 4; | |
CONST CORNER_BR = 8; | |
CONST SIDE_TOP = 16; | |
CONST SIDE_BOTTOM = 32; | |
CONST SIDE_LEFT = 64; | |
CONST SIDE_RIGHT = 128; | |
CONST ENCLOSED = 256; | |
/** | |
* @var point | |
*/ | |
public $tl = null; | |
/** | |
* @var point | |
*/ | |
public $br = null; | |
/** | |
* Accepts: | |
* + no arguments | |
* + four arguments, each a coordinate: x1 y1, x2 y2 | |
* + two arguments, each a point instance | |
* @return rect | |
*/ | |
public function __construct() { | |
$this->tl = new point(); | |
$this->br = new point(); | |
$nargs = func_num_args(); | |
$args = func_get_args(); | |
if( $nargs === 4 ) { | |
foreach( $args as $k => $arg ) { | |
if( ! is_numeric( $arg ) ) { | |
throw new Exception( 'bad point argument; not numeric' ); | |
} | |
switch( $k ) { | |
case 0: | |
$this->tl->x = $arg; | |
break; | |
case 1: | |
$this->tl->y = $arg; | |
break; | |
case 2: | |
$this->br->x = $arg; | |
break; | |
case 3: | |
$this->br->y = $arg; | |
break; | |
} | |
} | |
} else if( $nargs === 2 ) { | |
foreach( $args as $k => $arg ) { | |
if( ! ($arg instanceof point) ) { | |
throw new Exception( 'bad point argument; not instance of point' ); | |
} | |
switch( $k ) { | |
case 0: | |
$this->tl = $arg; | |
break; | |
case 1: | |
$this->br = $arg; | |
break; | |
} | |
} | |
} | |
} | |
/** | |
* Returns the area of the rectangle. | |
* | |
* @return double | |
*/ | |
public function area() { | |
return abs( $this->tl->x_delta( $this->br ) * $this->tl->y_delta( $this->br ) ); | |
} | |
/** | |
* Determines if $other collides with this rectangle. If there is collision then $other | |
* is split into a number of non-colliding rectangles and the colliding rectangle is left out. | |
* If $collision is not specified then a call to $this->collision( $other ) will be made. | |
* | |
* Returns an array of non-colliding rectangles, returns an empty array if the entirety of $other | |
* fits in $this, returns false if there is no split to be made. | |
* | |
* @param rect $other | |
* @param [int] $collision | |
* @return rect[] | false | |
*/ | |
public function split( rect $other, $collision = null ) { | |
if( $collision === null ) { | |
$collision = $this->collision( $other ); | |
} | |
// | |
if( $collision <= 0 ) { | |
$rv = false; | |
} else if( self::ENCLOSED & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ), | |
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $this->br->y ), | |
new rect( $this->br->x, $this->tl->y, $other->br->x, $this->br->y ) | |
); | |
} else if( self::CORNER_BL & $collision && self::CORNER_BR & $collision && self::CORNER_TL & $collision && self::CORNER_TR & $collision ) { | |
$rv = array(); | |
} else if( self::CORNER_TR & $collision && self::CORNER_BR & $collision ) { | |
$rv = array( new rect( $other->tl->x, $other->tl->y, $this->tl->x, $other->br->y ) ); | |
} else if( self::CORNER_TL & $collision && self::CORNER_BL & $collision ) { | |
$rv = array( new rect( $this->br->x, $other->tl->y, $other->br->x, $other->br->y ) ); | |
} else if( self::CORNER_BL & $collision && self::CORNER_BR & $collision ) { | |
$rv = array( new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ) ); | |
} else if( self::CORNER_TL & $collision && self::CORNER_TR & $collision ) { | |
$rv = array( new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) ); | |
} else if( self::CORNER_TL & $collision ) { | |
$rv = array( | |
new rect( $this->br->x, $other->tl->y, $other->br->x, $this->br->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::CORNER_TR & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $this->br->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::CORNER_BL & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $this->br->x, $this->tl->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::CORNER_BR & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $other->br->y ) | |
); | |
} else if( self::SIDE_TOP & $collision && self::SIDE_BOTTOM & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $other->br->y ), | |
new rect( $this->br->x, $other->tl->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::SIDE_LEFT & $collision && self::SIDE_RIGHT & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::SIDE_LEFT & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $this->br->x, $this->tl->y, $other->br->x, $this->br->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::SIDE_RIGHT & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ), | |
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $this->br->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::SIDE_TOP & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $this->br->y ), | |
new rect( $this->br->x, $other->tl->y, $other->br->x, $this->br->y ), | |
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) | |
); | |
} else if( self::SIDE_BOTTOM & $collision ) { | |
$rv = array( | |
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $other->br->y ), | |
new rect( $this->br->x, $this->tl->y, $other->br->x, $other->br->y ), | |
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ) | |
); | |
} | |
return $rv; | |
} | |
/** | |
* Calculates the collision of this rectangle with another. Returns an integer greater | |
* than zero if there is a collision. Use bitmask comparison of the return value against | |
* the CORNER_* class constants to determine which corners of $other are inside this | |
* rectable object. | |
* | |
* When rect::ENCLOSED bit is set it means $other encloses $this | |
* | |
* @param rect $other | |
* @return int | |
*/ | |
public function collision( rect $other ) { | |
$rv = 0; | |
// Check for complete miss | |
if( | |
$other->br->x <= $this->tl->x // right side of other is completely to left of this | |
|| $other->tl->x >= $this->br->x // left side of other is completely to right of this | |
|| $other->br->y <= $this->tl->y // bottom side of other is completely above this | |
|| $other->tl->y >= $this->br->y // top side of other is completely below this | |
) { | |
// no op, complete miss | |
} else { | |
$ls = $other->tl->x >= $this->tl->x && $other->tl->x <= $this->br->x; // left side of other intersects | |
$rs = $other->br->x >= $this->tl->x && $other->br->x <= $this->br->x; // right side of other intersects | |
$ts = $other->tl->y >= $this->tl->y && $other->tl->y <= $this->br->y; // top of other intersects | |
$bs = $other->br->y >= $this->tl->y && $other->br->y <= $this->br->y; // bottom of other intersects | |
$ls ? ($rv |= self::SIDE_LEFT) : false; | |
$rs ? ($rv |= self::SIDE_RIGHT) : false; | |
$ts ? ($rv |= self::SIDE_TOP) : false; | |
$bs ? ($rv |= self::SIDE_BOTTOM) : false; | |
$ls && $ts ? ($rv |= self::CORNER_TL) : false; // top left corner intersection test | |
$rs && $ts ? ($rv |= self::CORNER_TR) : false; // top right corner intersection test | |
$ls && $bs ? ($rv |= self::CORNER_BL) : false; // bottom left intersection test | |
$rs && $bs ? ($rv |= self::CORNER_BR) : false; // bottom right intersection test | |
$other->tl->x <= $this->tl->x && $other->tl->y <= $this->tl->y && $other->br->x >= $this->br->x && $other->br->y >= $this->br->y ? ($rv |= self::ENCLOSED) : false; | |
} | |
return $rv; | |
} | |
public function __toString() { | |
return "{$this->tl}, {$this->br} area( " . $this->area() . " )"; | |
} | |
} | |
$p = new proggy(); | |
$p->execute(); | |
?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment