XXI Open Cup Grand Prix of Korea K.Sewing Graph

二位平面上 $n$ 个点, 两两不重叠, 要求用两种颜色的边分别把他们连成一个连通块. 连边操作用一个 长度为 $k \ge 2$ 的序列 $s_i$ 表示, 方法如下:

1. 第一种颜色: 对所有 $1 \le i \le \left\lfloor \frac{k}{2} \right\rfloor$, $s_{2i−1}$ 和 $s_{2i}$ 连边
2. 第二种颜色: 对所有 $1 \le j \le \left\lfloor \frac{k-1}{2} \right\rfloor$, $s_{2j}$ 和 $s_{2j+1}$ 连边

求一个最短的序列 $s_i$, 满足上述条件, 且要求序列中相邻两个点不同, 对于同一种颜色, 连得边仅在端点处有相交.

$2 \le n \le 10^4$

题解

考虑最短序列, 应该为 $2n - 1$. 尝试这样是否可行. 从点数很少时手玩, 从简单的方向入手, 尝试构造两条链, 发现确实可行. 不考虑相交的话, 可以这样构造: $1, 2, \dots, n-1, n, n-1, \dots 2, 1$. 而且这两条链是一模一样的. 那么只需要考虑一条链不相交即可.

对点做一个双关键字排序, 从小到大连边, 这样就不会相交了.

复杂度 $O(n \log n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int n;

struct Node {
  PII p;
  int id;
  bool operator < (const Node &N) const {
    return p < N.p;
  }
} points[MAXN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    points[i] = {{x, y}, i};
  }
  sort(points + 1, points + 1 + n);
  printf("%d\n", 2 * n - 1);
  for (int i = 1; i <= n; i++)
    printf("%d ", points[i].id);
  for (int i = n-1; i; i--)
    printf("%d%c", points[i].id, " \n"[i==1]);
  return 0;
}