Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/python
- '''Solver for problem 2 of http://www.iarcs.org.in/inoi/2015/zco2015/zco2015-afternoon.pdf.'''
- import random
- SIZE = (100000, 500)
- def random_points(N):
- '''Return a list of N random points (tuples x,y).'''
- points = set()
- for dummy_i in range(N):
- insertion_todo = True
- while insertion_todo:
- point = (random.randint(1, SIZE[0]-1), random.randint(1, SIZE[1]-1))
- if not point in points:
- points.add(point)
- insertion_todo = False
- return list(points)
- def remove_same_x_value(points):
- '''
- Return a list where points with identical x value and higher y are removed
- and the list is sorted by x value (descending).
- '''
- # sort by x and then y value; use pythons dictionary ordering
- ordered = sorted(points, reverse=True)
- # create new list with first element already included
- cleaned = [ordered[0]]
- for point in ordered:
- if point[0] == cleaned[-1][0]:
- # if the current point has the same x value, use its lower y value
- cleaned[-1] = point
- else:
- # otherwise (new x value), add it
- cleaned.append(point)
- return cleaned
- def max_rectangle(points):
- '''
- Return the largest possible rectangle area from a list of points.
- Algorithm: Try to use points from right to left in the rectangle.
- - If there are more points for one x value, only the one with lowest y
- value is used.
- - First check the extreme x points; most right and most left, spanning
- a rectangle to the resp. limits.
- - Then go the the rightmost point and try to build a rectangle including it.
- There are two possibilities:
- - this point is on a horizontal edge
- Find its two neighbours, left and right, that have lower y value,
- as points on the left resp. right edge. If there is no
- left/right neighbour, use the end of the space.
- - this point is on a vertical edge
- Find the next-left point, use limit of the space as horizontal
- edge.
- '''
- # order and clean (remove points with same x value) points
- clean_points = remove_same_x_value(points)
- # compute area right of most-right point
- max_x = clean_points[0]
- area_right = (SIZE[0] - max_x[0]) * SIZE[1]
- # compute area left of most-left point
- min_x = clean_points[-1]
- area_left = min_x[0] * SIZE[1]
- max_area = max(area_right, area_left)
- #print('area left: {:.2e}, right: {:.2e}'.format(area_left, area_right))
- # now try to include each point in the rectangle
- for index in (range(len(clean_points))):
- # use point as on horizontal edge
- upper_edge_index = index
- height = clean_points[upper_edge_index][1]
- left = None
- right = None
- # search left neighbour (increasing index)
- for left_edge_index in range(upper_edge_index, len(clean_points)):
- if clean_points[left_edge_index][1] < height:
- left = clean_points[left_edge_index][0]
- break
- # if unable to find a left border, use the border of the area
- if left is None:
- left = 0
- # search right neighbour:
- for right_edge_index in range(upper_edge_index-1, 0-1, -1):
- if clean_points[right_edge_index][1] < height:
- right = clean_points[right_edge_index][0]
- break
- # if unable to find a right border, use the border of the area
- if right is None:
- right = SIZE[0]
- # compute area of this found rectangle
- area = (right - left) * height
- #print('Found bounded rectangle between x {}, {} and height {}; area {:.2e}'.format(left, right, height, area))
- if area > max_area:
- max_area = area
- # use point as on vertical edge
- right_edge = clean_points[index][0]
- # next vertical edge is simply next point
- try:
- left_edge = clean_points[index + 1][0]
- area = (right_edge - left_edge) * SIZE[1]
- #print('Found open rectangle between x {}, {}; area {:.2e}'.format(left_edge, right_edge, area))
- if area > max_area:
- max_area = area
- except IndexError:
- # no next edge; this is the leftmost-case from above...
- pass
- return max_area
- # actual program
- def run_random(N):
- print('Running for {} points (area {})'.format(
- N, max_rectangle(random_points(N))))
- def run_random_silent(N):
- max_rectangle(random_points(N))
- # Run from command line with first argument as number of points to create.
- import sys
- run_random(int(sys.argv[1]))
- # Simple tests
- def test_max_rectangle():
- assert max_rectangle([(1, 4), (2, 3), (3, 2), (5, 1), (5, 2)]) == 49997500, 'test case from problem'
- assert max_rectangle([(90000, 4)]) == 90000 * SIZE[1], 'biggest rectangle to the left'
- print('test')
- assert max_rectangle([(3, 25), (SIZE[0] - 10, 13)]) == (SIZE[0] - 10 - 3) * SIZE[1], 'biggest rectangle open in middle'
- assert max_rectangle([(5, 90), (45000, 428), (99000, 33)]) == (99000 - 5) * 428, 'biggest rectangle bounded in middle'
- def test_remove_same_x_value():
- assert remove_same_x_value([(3,3), (3,4)]) == [(3,3)], 'remove x values 1'
- assert remove_same_x_value([(2,1), (2,5), (3,5), (3,4)]) == [(3,4), (2,1)], 'remove x values 2'
- def tests():
- test_max_rectangle()
- test_remove_same_x_value()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement