Galactic Confederation
Time limit2sMemory limit512 MB
Given M planes and N planet positions, count how many planets fall in the most populated region formed by the planes.
- Level
Medium4 of 10
- Topics
- Geometry, Hash map, Brute force, Implementation
- Solved
- No attempts yet
Problem
The Galactic Confederation reorganized its administration to spread the resources of its fleet more evenly. It started by cutting all of space into regions. A set of infinite planes was fixed first, and every piece those planes cut space into is one region. Some regions are unbounded, and bounded regions can appear too.
The planes were chosen so that no plane meets the orbit of any planet. Each planet therefore stays inside a single region for its whole orbit. A planet inside a region never crosses a plane into another region.
Given the equations of the planes and the positions of the planets, find how many planets lie in the region that holds the most planets.
Input
The first line has two integers and , the number of planes and the number of planets. (, )
Each of the next lines has four integers , , , , the coefficients and the constant term of the equation of one plane. ()
Each of the following lines has three integers , , , the position of one planet. ()
Output
Print one line with a single integer, the number of planets in the region that contains the most planets.