moakhey's blog

By moakhey, history, 9 years ago, In English

Hello, I've been trying to solve this problem on POJ: http://poj.org/problem?id=2084 After few drawings I understood that i should calculate the catalan number of the given n, however I got a WA. I think its because the size of the numbers which exceed the long long unsigned limit. What should I do? Am i wrong or should I operate on strings instead and perform my own multiplication?

Full text and comments »

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

By moakhey, 10 years ago, In English

Hi, I was thinking about this problem: given a set of points in a plane, find the two points which are the farthest from each other. Logically, these two points should lay on the convex hull, so I came up with a solution with NlogN complexity: for each point A0 on the convex hull, do a binary search to find the farthest point from A0. (We have the set of points on the convex hull ordered such that they form a cycle). We take the point in the middle of index i, if d(A0,Ai)>d(A0,A(i+1)) then we should only consider the points A1..Ai, otherwise we only consider points Ai..An, and we repeat recursively until we get only one point. I think i have a simple proof by contradiction, but I want your opinion about its correctness/efficiency.

Full text and comments »

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