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

GEOMETRY — Visit n points in some order (help)
Автор watchyour6, история, 4 года назад, По-английски

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

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

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

use the onion-decomposition

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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) .

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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.

→ Ответить