Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2188
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2188
Capuchin Monkey
Por OBI - Olimpíada Brasileira de Informática 2000 
Brazil
Timelimit: 1
The capuchin monkey is a pet restless and noisy, worthy also of disorderly and unashamed adjectives. His head, surmounted by thick black or dark brown coat, similar to a cap, makes its unmistakable appearance. Despite being the most common monkey in the forests of the country, one of his sub-species is seriously endangered: the capuchin monkey yellow breast, which distinguishes itself by yellowing of the chest and the front of the arms.
A great effort was made by primatologists to increase the population of capuchin monkeys-of-yellow-breast. It is known that they feed on plants, which consume preferably fruits and sprouts. They feed too many animals, preferably slugs, caterpillars and frogs, and prefer the densest forests. To determine the best place in the country to create a new environmental reserve for capuchin monkeys-of-yellow-breast, the government made a survey of the regions in the country where the preferred conditions of these animals occur: regions of dense forest regions with fruits , regions with many shoots, etc. Help to save the capuchin-monkeys-of-yellow-breast.
The regions suitable for the capuchin monkey-of-yellow-breast were determined as rectangles whose sides are all vertical or horizontal. Your task is to find the ideal place for environmental reserves, defined as the intersection of all the given regions.
The regions were divided so that a region not tangent to any other region. Thus the intersection of any two or regions is a rectangle or is empty.
Input
Your program must read multiple test sets. The first line of a test set contains a non-negative integer, N (0 ≤ N ≤ 10000), that indicates the number of regions (the value N = 0 indicates the final of the input). It follows N lines, each one contains four integer numbers X, Y, U e V (-10000 ≤ X,Y,U,V ≤ 10000) that describe a region: the pair X, Y represents the coordinate of the upper left corner and the pair U, V represents the coordinate of the upper right corner and the pair
For each input test set your program must produce three lines in the output. The first line should contain a test set identifier in the format "Teste n", where n is numbered from 1. The second line should contain the intersection rectangle coordinates found by your program in the same format used in entry . If the intersection is empty, the second line should contain the word "nenhum". The third line should be left blank. The spelling shown in Output Sample below should be followed strictly.
| Input Sample | Output Sample |
|
3 0 6 8 1 1 5 6 3 2 4 9 0 3 0 4 4 0 3 1 7 -3 6 4 10 0 0 |
Teste 1 2 4 6 3 Teste 2 nenhum |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define INF 10010
#define NEGINF -INF
int main() {
int teste = 1, n;
while (scanf("%d", &n) && n) {
printf("Teste %d\n", teste++);
int x1 = NEGINF, y1 = INF, x2 = INF, y2 = NEGINF;
for (int k = 0; k < n; k++) {
int x3, y3, x4, y4;
scanf("%d %d %d %d", &x3, &y3, &x4, &y4);
if (x3 > x1) x1 = x3;
if (y3 < y1) y1 = y3;
if (x4 < x2) x2 = x4;
if (y4 > y2) y2 = y4;
}
if (x1 > x2 || y2 > y1)
printf("nenhum\n\n");
else
printf("%d %d %d %d\n\n", x1, y1, x2, y2);
}
return 0;
}
Input
0 6 8 1
1 5 6 3
2 4 9 0
3 0 4 4 0
3 1 7 -3
6 4 10 0
0
Output
2 4 6 3
Teste 2
nenhum