[ED217] Geometria

Neste problema deverá submeter um programa inteiro implementado numa classe chamada Geometry (incluindo a classe main, a leitura de input e a escrita de output). Deve submeter apenas esta classe (pode assumir que no Mooshak terá acesso às classes auxiliares Point e Rectangle)

Código Base

O seu programa deve usar as classes Point e Rectangle como estão a seguir definidas. Se não usar as classes dadas, não obterá pontuação neste problema (note também que não pode alterar as classes dadas: apenas deverá usá-las).

// Uma classe simples para representar um ponto 2D
class Point {
    private int x, y; // Coordenadas do ponto

    // Construtor de um ponto
    Point(int x0, int y0) {
	x = x0;
	y = y0;
    }

    // Getters
    int getX() { return x; }
    int getY() { return y; }
   
    // Devolve uma representação em texto do conteúdo de um ponto
    public String toString() {
	return "(" + x + "," + y + ")";
    }
}

// Uma classe simples para representar um rectângulo
class Rectangle {
    Point p1, p2; // Ponto inferior esquerdo e ponto superior direito

    // Construtor de um rectângulo
    Rectangle(Point a, Point b) {
	p1 = new Point(a.getX(), a.getY());
	p2 = new Point(b.getX(), b.getY());
    }

    // Área de um rectângulo
    int area() {
	return (p2.getX()-p1.getX()) * (p2.getY()-p1.getY()); 
    }

    // Perímetro de um rectângulo
    int perimeter() {
	return (p2.getX()-p1.getX())*2 +  (p2.getY()-p1.getY())*2;
    }

    // Devolve true se o ponto p está dentro do rectângulo e false caso contrário
    // Se estiver na borda é considerado que está dentro
    boolean pointInside(Point p) {
	return (p.getX() >= p1.getX() && p.getX() <= p2.getX() &&
		p.getY() >= p1.getY() && p.getY() <= p2.getY());
    }

    // Devolve true se o rectângulo r está dentro do rectângulo e false caso contrário
    boolean rectangleInside(Rectangle r) {
	return pointInside(r.p1) && pointInside(r.p2);
    }
}

O problema

Dado um conjunto de pontos e rectângulos, a sua tarefa é contar quantos pontos não estão dentro de nenhum rectângulo, e quantos rectângulos não contêm nenhum ponto. Note que se um ponto estiver exactamente na borda de um rectângulo, é considerado que está dentro do rectângulo.

Considere por exemplo a figura seguinte. Neste exemplo temos exactamente um ponto que não está dentro de nenhum rectângulo (o ponto D) e dois rectângulos que não contêm nenhum ponto (o azul e o vermelho).

Input

Na primeira linha vem um número P indicando o número de pontos a considerar (1≤P≤100), seguida de N linhas, cada uma contendo dois inteiros X_i e Y_i indicando as coordenadas do ponto.

Segue-se uma linha contendo R indicando o número de rectângulos a considerar (1≤R≤100), seguida de N linhas, cada uma contendo quatro inteiros X1_i Y1_i X2_i Y2_i, representando respectivamente o ponto inferior esquerdo e o ponto superior direito do rectângulo.

É garantido que as coordenadas serão todas inteiros positivos entre 1 e 1000000 (inclusive).

Output

O output deverá ser uma única linha com dois inteiros separados por um espaço: o primeiro inteiro deve indicar o número de pontos que não estão dentro de nenhum rectângulo, e o segundo inteiro deve indicar o número de rectângulos que não contêm nenhum ponto.

Exemplo de input/output

4
1 1
2 2
3 4
8 2
5
1 1 3 4
2 3 9 6
3 4 4 5
5 1 6 6
7 3 9 5

Este exemplo corresponde à figura do enunciado.

Última actualização: