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

Автор SPyofgame, история, 3 года назад, По-английски

The problem

Given $$$n$$$ points $$$(x_1, y_1),\ (x_2, y_2),\dots, (x_n, y_n)$$$

Find the minimum distance between 2 pair of points.

The problem: SPOJ



The constraint

  • $$$2 \leq n \leq 50000$$$

  • $$$x_i, y_i \leq 10^6$$$



My question

I was solving a problem that need to find the minimum distance between two points. I tried to bruteforce then cde an divide and conquer algorithm. But then I modified the bruteforce by adding some branch-and-bound to ignore not-optimal cases. For somehow my code get AC and seems to run fast while I thought it will be slow with the complexity of $$$O(n^2)$$$ with small constant.

I dont really sure about the complexity, can some one help me to calculate it ?

My main part
My full code
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Same idea here.