watchyour6's blog

GEOMETRY — Visit n points in some order (help)
By watchyour6, history, 4 years ago, In English

Given $$$N$$$ points in $$$2D$$$ plane with integer coordinates. Initially you are at a point $$$p1$$$ , visit all remaining $$$n-1$$$ points and come back to $$$p1$$$ . Between two points you move in a straight line joining them . Only constraint is that no two of the lines must intersect .
Constraints:
$$$3 ≤ N ≤ 1000$$$
$$$-1,000,000 ≤ x i , y i ≤ 1,000,000 $$$
Problem Link — Mission-Infoarena
Some help is appreciated as im stuck so bad.

UPD: Solved

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

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

use the onion-decomposition

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We need to come back to the point we started from, Is it possible moving this spiral way? Also, the starting point is fixed( first point in the input) .

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

      if you are at a point p1 and you want to go to another spiral (the one above or below it) you should find the closest point in that spiral to p1 and go to it, try to work by hand some examples and you will see it's always possible no matter where you start.

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

        I just realised , the complexity will be $$$O(n^2)$$$ . Thanks for the help.

        → Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

You forgot to mention the constraint that no three points are collinear. Pick the leftmost point and put it as the first point, then sort all other points by angle, and visit them in this order.

→ Reply