PraveenDhinwa's blog

SPOJ MPOLI

By PraveenDhinwa, 13 years ago, In English

Hi guys ,,, Could anybody help me How to solve http://www.spoj.pl/problems/MPOLY/ . I tried to relate it with convex Hull ,, But It did not work . There is a codeforces blog on dp problems ,which suggests it to be a geometry dp problem ,, Any hints please!!!!!! Any kind of help will be appreciated . Thank you.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

1) consider point (0, 0) as center of our plane.
2) sort points by angle
3) add point (0, 0) at first position of array Let DP(a, b) — maximal possible number of points which can be added. (a < b)
(small letters are indexes, while capital letters are points, with corresponding indexes)
We can add point C if and angle Alpha ABC is 0 < Alpha < 180.
1) if we cannot add any point we have to add point (0, 0) if we can, otherwise answer is -infinity
2) try to add any point C, such that b < c and chose maximal anser pseudocode:

DP(a, b)
{
  if (calculated[a][b])
    return dp[a][b];
  res = -infinity;
  if (Can(p[a], p[b], Point(0, 0))) res = 0;
  for (c = b + 1; c < n; c++)
    if (Can(p[a], p[b], p[c]))
      res = max(res, DP(b, c));
  calculated[a][b] = true;
  dp[a][b] = res;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    How do you sort by angle? I am trying to solve it this way! I am getting WA all the time.

    What am I doing wrong?
    Than n is actually '\n'. I don't know how to print it using some escape sequence here.

    My Code
    → Reply