Marbles
Time limit1sMemory limit256 MB
Place three pairwise disjoint axis-aligned rectangles to maximize red marbles in the first plus blue in the second plus green in the third.
- Level
Hard8 of 10
- Topics
- Geometry, Prefix sum, Brute force
- Solved
- No attempts yet
Problem
Three children A, B, and C play with marbles. Every marble is red, blue, or green. At the start of the game the marbles are thrown on the ground and scatter. No two marbles share the same coordinate, and no two share the same coordinate.
A, B, and C each draw one rectangular area on the ground. The sides of a rectangle are parallel to the axes, and the area is a closed region that contains its boundary. No two of the three rectangles may share even a single point. A rectangle can shrink to one point.
Child A then counts only the red marbles inside their own area, B counts only the blue marbles inside theirs, and C counts only the green marbles inside theirs. A child may count zero marbles. The goal of the game is to make the total number of counted marbles as large as possible.
Write a program that computes the largest total the three children can count.
Input
The first line contains the number of test cases .
Each test case starts with a line holding three integers , , and (), the numbers of red, blue, and green marbles. Each of the next lines holds two integers and , the position of a red marble. The next lines give the blue marbles in the same format, and the next lines give the green marbles. Every coordinate satisfies .
Inside one test case, at most one marble lies on any horizontal line and at most one marble lies on any vertical line.
Output
For each test case, print one line with the maximum total number of counted marbles.