PROG0326 - Collision detection
What does it mean for two objects to collide? This is an import question in many applications, which cannot always be answered easily by a computer program. If two planar objects overlap, this is called a collision. You should not take this too literally and immediately think about two cars that crashed against each other. Collision detection can be used for example to determine whether one region is contained within another region on a map, or to analyse images.
For this exercise, we consider the simplest form of collision detection. In this, each object is represented by its axis-aligned bounding box. This is the smallest rectangle that contains the entire object and has edges parallel to the $X$- and $Y$-axis. We say that two objects collide if their bounding boxes overlap.
Input
The input contains eight integers (each on a separate line) that represent two diametrical points of two rectangles. Each point is described by two consecutive integers, with the first being the $x$ co-ordinate and the second the $y$ co-ordinate. The rectangles are real rectangles and are not degenerate as a line segment or a point.
Output
There is only one single line of output. This line contains the text collision if the two given rectangles overlap, and the text no collision if the two rectangles do not overlap. Note: touching rectangles do not overlap!
Example
Input:
0
0
1
2
4
1
5
5
Output:
no collision
Example
Input:
0
0
2
3
1
2
5
5
Output:
collision
Wat is de onderlinge positie van twee gegeven objecten? Het is een belangrijke vraag, die niet altijd even makkelijk te beantwoorden is door een computerprogramma. Als twee objecten in het vlak overlappen, dan noemen we dit een botsing. Je moet dit echter niet te letterlijk opnemen en direct denken aan twee auto's die elkaar aangereden hebben. Een botsing kan bijvoorbeeld ook gebruikt worden om te bepalen of twee onderdelen op een kaart in elkaar liggen, of om delen van foto's te analyseren.
Bij deze opgave gaan we een vereenvoudigde versie van het probleem bekijken. We stellen een object voor door zijn axis-aligned bounding box. Dit is de rechthoek die net het object omsluit en waarvan de zijden evenwijdig zijn met de $X$- en $Y$-as. We zeggen dan dat twee objecten botsen als hun bounding boxes overlappen.
Invoer
De invoer bestaat uit acht gehele getallen (één per regel) die tweemaal twee diametrale punten van twee rechthoeken voorstellen. Het eerste getal is telkens de $x$-coördinaat en het tweede getal de $y$-coördinaat. De rechthoeken zijn echte rechthoeken (en dus niet ontaard als lijnstuk of punt).
Uitvoer
De uitvoer bestaat uit één regel. Deze regel bevat de tekst botsing als de twee rechthoeken overlappen en de tekst geen botsing als de twee rechthoeken niet overlappen. Opgelet: raken is niet overlappen!
Voorbeeld
Invoer:
0
0
1
2
4
1
5
5
Uitvoer:
geen botsing
Voorbeeld
Invoer:
0
0
2
3
1
2
5
5
Uitvoer:
botsing
Added by: | Peter Dawyndt |
Date: | 2013-02-13 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | PY_NBC |
Resource: | None |