All submissions for this problem are available.
Given a convex polygon with N vertices. We have M Queries. In each Query, we are given a point P which is inside the polygon. This point P can be represented as Linear Combination of N vertices of polygon. We need to find the N coefficients in each Query.
P(X, Y) = A1 * (X1, Y1) + A2 * (X2, Y2) + ..... + An * (Xn, Yn).
where 0 <= Ai <= 1
Find A1, A2, A3, .... , An
First Line contains an integer N
Next N Lines contain the vertices of the convex polygon. All the vertices of the polygon are in the anti-clockwise order
Next line contains the M
Next M lines contains a point inside of the polygon
For each Query, print N coefficients in a line
P'(X', Y') is the estimated point. Answer is correct if abs(X'-X) <= 10^-6 and abs(Y' - Y) <= 10^-6
- 3 ≤ N ≤ 10000
- 1 ≤ M ≤ 1000
Input: 4 0 0 2 0 2 2 0 2 1 1 1 Output: 0.5 0 0.5 0
|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.