Блог пользователя PraveenDhinwa

Автор PraveenDhinwa, 13 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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;
}
  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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