m.ajaj94's blog

Help with array problem
By m.ajaj94, history, 8 years ago, In English

Hello there

I have a 2D array with dimensions 2500*2500

And i have n < 10000

Now i am given an initial point in the array in the form of x,y and i need to find n points in the array that all points are as far from each other as possible

Bottom line is : i have an array and i need to find n positions in it as scattered as possible

This is not a problem i found on an online judge it's for a project i'm doing and im wondering if theres a way to accomplish this in reasonable complexity

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

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What does "as far from each other as possible" mean? Are you looking to maximize average distance, smallest distance between a pair, or something else?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Smallest distance between any pair

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So what is the maximum number of points in the array? I couldn't quite figure it out from your post. Is it 2500*2500?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        10000

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          So you want to find a set of points of given size (between 1 and 10000) that has the greatest shortest distance between any pair of points, right?

          → Reply