International Cancer Pathology Company (ICPC) es una empresa dedicada a desarrollar modelos de inteligencia artificial (AI) para detectar células cancerosas en imágenes patológicas de tumores. En la fase de preprocesamiento, el modelo AI detecta núcleos celulares en una imagen patológica y utiliza un llamado «cuadro delimitador» para encerrar cada núcleo, como muestra la figura 12. Un cuadro delimitador es un rectángulo representado mediante una 4-tupla $(x_1,y_1,x_2,y_2)$, donde $(x_1,y_1)$ son las coordenadas de su esquina superior izquierda y $(x_2,y_2)$ las de su esquina inferior derecha. Un cuadro delimitador dibujado por el modelo AI se llama cuadro delimitador detectado.
Figura 12: Una imagen patológica con cuadros delimitadores detectados.*
Para evaluar el rendimiento del modelo AI, los investigadores de ICPC prepararán un conjunto de datos de prueba (imágenes patológicas), y expertos médicos ayudarán a anotar previamente la verdad de referencia (los núcleos celulares reales) mediante cuadros delimitadores. Estos se llaman cuadros delimitadores de referencia. Después, los investigadores aplicarán el modelo AI para detectar núcleos celulares en el conjunto de prueba y comprobar cuántos núcleos de referencia se detectan. Decimos que un núcleo cuyo cuadro delimitador de referencia es $G$ ha sido detectado por el modelo AI si existe un cuadro delimitador detectado $D$ que se solapa con $G$ en al menos la mitad del área de $G$, es decir, $|D\cap G|/|G|\ge1/2$. Observa que un cuadro detectado puede solaparse con dos o más cuadros de referencia, pero solo uno puede considerarse detectado por ese cuadro detectado. La figura 13 muestra un ejemplo de cuadros de referencia y detectados. Además, la anchura y la altura de un cuadro delimitador tienen un límite, ya que el tamaño de los núcleos celulares es limitado.
Dados un conjunto de cuadros delimitadores de referencia y otro de cuadros delimitadores detectados, escribe un programa que determine el máximo número de núcleos celulares detectados.
Entrada
La primera línea contiene un entero $t$, que representa el número de casos de prueba. Para cada caso, la primera línea contiene dos enteros $m$ y $n$ separados por un espacio, que representan las cantidades de cuadros de referencia y detectados, respectivamente. Las siguientes $m+n$ líneas representan las 4-tuplas $(x_1,y_1,x_2,y_2)$ de coordenadas de los cuadros, con un espacio entre cada par de enteros consecutivos. Las primeras $m$ líneas representan los cuadros de referencia y las siguientes $n$ líneas los cuadros detectados.
- Las imágenes de las figuras se citan del artículo disponible en la URL: https://www.kitware.com/cell-nuclei-detection-on-whole-slide-histopathology-images-using-histomicstk-and-faster-r-cnn-deep-learning-models/
Figura 13: Una imagen patológica con cuadros delimitadores de referencia (cuadros azules) y cuadros delimitadores detectados (cuadros verdes).*
Restricciones
$1\le t\le5$.
$1\le m,n\le50\,000$.
$0\le x_1,y_1,x_2,y_2\le2000$.
Las variables $t,m,n,x_1,y_1,x_2,y_2$ son enteros.
La longitud máxima de la anchura y de la altura de un cuadro delimitador es 4.
No hay dos cuadros de referencia con una relación de inclusión, es decir, uno no contiene al otro; tampoco hay dos cuadros detectados con esa relación.
Salida
Cada caso de prueba produce un entero $k$ en una línea, donde $k$ es el máximo número de núcleos celulares detectados por los cuadros detectados dados.
Ejemplos
Entrada 1
3 2 2 1 1 3 3 3 3 5 5 2 2 4 4 4 4 6 6 2 3 1 1 3 3 3 3 5 5 1 3 3 5 2 1 4 5 3 1 5 3 3 3 1 1 2 2 2 2 3 3 3 3 4 4 1 1 3 3 2 2 4 4 3 3 5 5
Salida 1
0 1 3