PROG0227 - Borders

To draw the map of a country, you need to determine a rectangle that encloses the whole country. This rectangle is called the bounding box of the country. If you know the $x$- and $y$-coordinates of some points that are on the border of the country, the sides of the bounding box can be found in the following way:

  • top: maximum of all $y$-coordinates
  • bottom: minimum of all $y$-coordinates
  • right: maximum of all $x$-coordinates
  • left: minimum of all $x$-coordinates

The position and size of a rectangle can be described by the coordinates of two of its opposing corner points. The bounding box of a country is thus fully described if you know two points: the point with the minimum of all $x$- and $y$-coordinates and the point with the maximum of all $x$- and $y$-coordinates.

Assignment

Write a function boundingbox that takes a list of tuples as its only argument. Each tuple contains two real-valued numbers that represent the coordinates of a point on the border of a country. The function must return the coordinates of the two opposing corner points that describe the bounding box of the country. The first corner point is the point with the minimum of all $x$- and $y$-coordinates and the second point is the point with with the maximum of all $x$- and $y$-coordinates. Inspect the examples below to find out the details about the return value of the function. If your answer is correct or incorrect, you will find on the feedback page a graphical representation of the bounding boxes as determined by your implementation.

Example

>>> boundingbox([(0.0, 1.0), (1.0, 0.0)])
[(0.0, 0.0), (1.0, 1.0)]
>>> border = [(51.2632, 4.3024), (51.3751, 4.2524), (51.4867, 5.0414),
...           (51.1564, 5.8492), (50.8397, 5.6408), (50.7573, 6.0118),
...           (50.3232, 6.3982), (50.1278, 6.1344),(50.1813, 6.0263),
...           (49.545, 5.8079), (49.7972, 4.8731), (50.1686, 4.8325),
...           (49.9784, 4.1492), (50.2831, 4.165), (51.0911, 2.5417),
...           (51.3739, 3.3709), (51.3504, 4.2389), (51.2632, 4.3024)]
>>> boundingbox(border)
[(49.545, 2.5417), (51.4867, 6.3982)]

Om de kaart van een land weer te geven heb je het kader nodig dat net rond dit land past. Dit kader noemt men de minimaal omschreven rechthoek (bounding box). Als je de $x$- en $y$-coördinaten kent van een aantal punten die op de landsgrens gelegen zijn, dan kan je de zijden van de minimaal omschreven rechthoek als volgt vinden.

  • bovenzijde: maximum van alle $y$-coördinaten
  • onderzijde: minimum van alle $y$-coördinaten
  • rechterzijde: maximum van alle $x$-coördinaten
  • linkerzijde: minimum van alle $x$-coördinaten

Een rechthoek kan je beschrijven aan de hand van twee coördinaten, namelijk de coördinaten van twee tegenoverstaande hoekpunten. Voor de omschreven rechthoek van een land betekent dit dus dat het voldoende is om twee punten te weten: het punt met als coördinaten de minima van alle $x$- en $y$-coördinaten en het punt met als coördinaten de maxima van alle $x$- en $y$-coördinaten.

Opgave

Schrijf een functie boundingbox waaraan als enige argument een lijst van tuples moet doorgegeven worden. Elk tuple bevat twee reële getallen die de coördinaten voorstellen van een punt dat op de landsgrens gelezen is. De functie moet de coördinaten van twee van de hoekpunten van de minimaal omschreven rechthoek voor deze punten teruggeven als een lijst van tuples van twee reële getallen. Het eerste hoekpunt is het punt met als coördinaten de minima van alle $x$- en $y$-coördinaten en het tweede punt is het punt met als coördinaten de maxima van alle $x$- en $y$-coördinaten. Bekijk ook het onderstaande voorbeeld.

Als je een correct antwoord hebt, kan je doorklikken om de omschreven rechthoeken te bekijken die je oplossing genereert.

Voorbeeld

>>> boundingbox([(0.0, 1.0), (1.0, 0.0)])
[(0.0, 0.0), (1.0, 1.0)]
>>> grens = [(51.2632, 4.3024), (51.3751, 4.2524), (51.4867, 5.0414),
...          (51.1564, 5.8492), (50.8397, 5.6408), (50.7573, 6.0118),
...          (50.3232, 6.3982), (50.1278, 6.1344),(50.1813, 6.0263),
...          (49.545, 5.8079), (49.7972, 4.8731), (50.1686, 4.8325),
...          (49.9784, 4.1492), (50.2831, 4.165), (51.0911, 2.5417),
...          (51.3739, 3.3709), (51.3504, 4.2389), (51.2632, 4.3024)]
>>> boundingbox(grens)
[(49.545, 2.5417), (51.4867, 6.3982)]

Added by:Peter Dawyndt
Date:2012-02-27
Time limit:12s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.