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)
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); } }
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).
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 Xi e Yi 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 X1i Y1i X2i Y2i, 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).
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.
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 |
1 2 |
---|
Este exemplo corresponde à figura do enunciado.
Última actualização: