Snowflake Tanghulu
InterviewTime limit2sMemory limit512 MB
Given fruit positions and candidate endpoints, find the most fruits one skewer from (0, 0) to a candidate endpoint can pierce.
- Level
Medium5 of 10
- Topics
- Hash map, Math, Sorting, Binary search
- Solved
- No attempts yet
Problem
Freshmen who entered Sookmyung Women's University like cute snowflakes, so they want to make snowflake tanghulu. Snowflake-shaped fruits are placed on a two-dimensional coordinate plane. A skewer runs from to an endpoint and pierces every fruit on the segment that includes that endpoint. There are candidate endpoint positions. Find the largest number of fruits that a single skewer can pierce, over all candidate endpoints.
Input
The first line contains the number of fruits and the number of candidate endpoints , both integers. (; ) The next lines each contain a fruit position , separated by a space. (, both integers.) No two fruits share the same position. The next lines each contain a candidate endpoint , separated by a space. (, both integers.) No two candidate endpoints are the same. No fruit or endpoint is . A fruit position and an endpoint may be the same point.
Output
Print the largest number of fruits that can be pierced by one skewer.