Rectangle contenidor mínim P84110


Statement
 

Graphic problem

pdf   zip

html

Donat un conjunt de punts en el pla, el seu rectangle contenidor mínim és el rectangle més petit amb costats paral·lels als eixos de coordenades que conté tots els punts. Donada una llista de p punts, podeu trobar el seu rectangle contenidor mínim?

Entrada

L’entrada comença amb dos enters n i p, seguits de p punts (xi, yi) amb coordenades entre 0 i n−1. Podeu assumir 1 ≤ n ≤ 500, 1 ≤ p ≤ n2, i que cap dels punts està repetit.

Sortida

Genereu una imatge de dimensions (n, n) amb fons ‘Beige’, seguint els exemples. Pinteu els punts de color ‘Black’, i el rectangle de color ‘Red’. Suposeu que els rectangles són tancats, és a dir, que els punts de la vora hi pertanyen.

Public test cases

  • Input

    20
7
10
5
2
14
1
1
8
15
6
6
9
15
8
14

    Output

    sample-1.png

     (20×20)

  • Input

    2
1
1
0

    Output

    sample-2.png

     (2×2)

  • Input

    2
1
0
0

    Output

    sample-3.png

     (2×2)

    • Information
    Author
    Víctor Martín
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python