7564. Distance on Triangulation

 

Given a regular polygon with n vertices. The vertices of the polygon are numbered consecutively from 1 to n. A triangulation of this polygon is also given in the form of a list of n − 3 diagonals.

There are q queries. Each query is specified by the numbers of two vertices. For each query, you need to determine the shortest distance between these two vertices, moving along the sides or the given diagonals of the polygon. The distance is defined as the total number of sides and diagonals traversed.

 

Input. The first line contains an integer n (4 ≤ n ≤ 50000) – the number of vertices of the polygon.

The next n – 3 lines each contain two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) – the endpoints of the i-th diagonal.

The next line contains an integer q (1 ≤ q ≤ 100 000) – the number of queries.

The next q lines contain two integers xi, yi (1 ≤ xi, yi ≤ n) – the vertices of the i-th query.

It is guaranteed that:

·        no diagonal coincides with a side of the polygon;

·        no two diagonals coincide or intersect.

 

Output. For each query, print one integer on a separate line – the shortest distance between the given vertices.

 

Sample input

Sample output

6

1 5

2 4

5 2

5

1 3

2 5

3 4

6 3

6 6

2

1

1

3

0

 

 

SOLUTION

geometry – recursion, divide and conquer

 

Анализ алгоритма

В любом триангулированном многоугольнике существует диагональ, которая отрезает от многоугольника минимум n / 3 вершин. Найдем диагональ (i, j), которая делит многоугольник на две части, модуль разницы количества вершин в которых минимален. Это будет такая диагональ (i, j), что расстояние от i до j по периметру многоугольника будет наибольшей. Выбор диагонали  произвольным образом даст Time Limit.

При помощи поиска в ширину за O(n) найдем кратчайшие расстояния от i и от j до всех вершин по сторонам и диагоналям многоугольника.

Разделим многоугольник на два по выбранной диагонали.Далее снова ищем в каждом из них диагональ, делящую по возможности пополам, с обоих концов диагоналей запускаем поиск в ширину и снова продолжаем делить многоугольники по диагонали. Процесс деления продолжаем, пока многоугольник не станет треугольником (не будет внутри себя содержать диагоналей триангуляции).

Глубина рекурсии составит O(log2n), в результате разрезаний получим O(n) многоугольников общего размера O(n log2n).

 

Рассмотрим запрос (x, y) – поиск кратчайшего расстояния от x до y. Если вершины запроса лежат по одну сторону от разделяющей диагонали (i, j), то решаем задачу в соответствующем многоугольнике. В противном случае кратчайший путь dist(x, y) от x до y обязательно будет проходить либо через i, либо через j. То есть

dist(x, y) = min (dist(x, i) + dist(i, y), dist(x, j) + dist(j, y))

Все расстояния в правой части равенства нам известны – мы их нашли поиском в ширину.

 

Пример

 

 

 

 

Реализация алгоритма