Dilku and Polygon
All submissions for this problem are available.
This time, Bhopu invited Dilku to a date in Hotel-Raj, the best hotel in Artland !!! While on his way to the hotel, Dilku saw a strange polygon. As Dilku loves polygons, he formulated a problem on it. Can you solve Dilku's problem ? Here it goes :
Given a convex polygon of N points , there are another K points given, lying inside the polygon.
Chose any pair of points among the given K points and any 1 point p among the N points of polygon.
Let M be the number of points of the polygon that are visible to us if we stand at point p and the line of sight should pass through the line segment formed by the pair of points chosen. Chose a combination of these points such that M is maximized.
The first line of the input contains 2 space separated integers N and K, N denoting the number of points of the polygon and K denoting number of points lying inside the polygon respectively.
Following N lines contains 2 space separated integers xi yi denoting the coordinates of points of the polygon in anticlockwise direction.
Following K lines contains 2 space separated integers xi yi denoting the coordinates of points inside the polygon.
Output a single integer M.
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 105
- -109 ≤ xi, xi ≤ 109
6 2 -6 13 -12 -6 14 -5 5 14 2 15 -4 14 -6 -3 -3 7
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.