题解：P1153 点和线

· · 题解

题解：P1153 点和线

题意简述

给你平面上的 n（n\le10）个点，你需要用 n 条边将它们连起来得到一个简单多边形，使得任意两边（除邻边外）无公共点。

这又有什么好简述的。

思路

考虑深搜，由于 n 较小，遍历所有方案的 O(n!) 的复杂度完全是可以接受的。

在此基础上考虑剪枝，不仅是因为能提高效率，还因为加了剪枝后代码稍微好写一些（确信）。

首先定义 dfs(int dep)，其中 dep 表示现在确定了多边形的前 dep-1 个顶点，现在应选择未选顶点中的一个作为第 dep 个顶点。决策时只需要判断当前点与上一个点的连边是否与其他已确定的边（除了邻边）是否有公共点即可。

判断两条线段是否有公共点非常简单，先考虑如何判断两条线段 AB 和 CD 是否相交。首先，两条线段相交，当且仅当点 C、D 分居 AB 两侧，且点 A、B 分居 CD 两侧。然后，C 和 D 分居 AB 两侧，当且仅当 \overrightarrow{AB}\times\overrightarrow{AC} 与 \overrightarrow{AB}\times\overrightarrow{AD} 异号，即 \left(\overrightarrow{AB}\times\overrightarrow{AC}\right)\left(\overrightarrow{AB}\times\overrightarrow{AD}\right)<0（其中“\times”号表示向量叉积）。而判断两条线段是否有公共点只需把上面式子中的小于号“<”改成小于或等于“\le”即可。代码如下：

int n;
bool check(point a, point b, point c, point d) {
    if(((b - a) * (c - a)) * ((b - a) * (d - a)) <= 0 && ((d - c) * (a - c)) * ((d - c) * (b - c)) <= 0) return true;
    return false;
}

其中代码中 b - a 表示由点 A 指向 B 的向量，即向量 \overrightarrow{AB}。

搜索共 n 层，每层最多可能决策 n 个点，总方案数约为 n!，故时间复杂度为 O(n!n^2)，但实际上因为有剪枝所以根本跑不满。

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
struct point { //定义点 or 向量
    int x, y;
    point operator + (point B) const { //向量加法（这不废话吗）
        return point {x + B.x, y + B.y};
    }
    point operator - (point B) const { //向量减法（废话）
        return point {x - B.x, y - B.y};
    }
    int operator * (point B) const { //向量叉积
        return x * B.y - y * B.x;
    }
} a[15];
int n;
bool check(point a, point b, point c, point d) { //判断线段 AB 与 CD 是否有公共点
    if(((b - a) * (c - a)) * ((b - a) * (d - a)) <= 0 && ((d - c) * (a - c)) * ((d - c) * (b - c)) <= 0) return true;
    return false;
}
bool vis[15];
point b[15];
int ans;
void dfs(int dep) { //搜索（还是废话） 
    if(dep == n) { //搜完后 
        for(int j = 2; j < dep - 1; j++) {
            if(check(b[j], b[j - 1], point {0, 0}, b[dep - 1])) {
                return ;
            }
        }
        ++ans; //记录答案 
        return ;
    }
    bool flag;
    for(int i = 1; i < n; i++) {
        if(vis[i]) continue;
        flag = true;
        for(int j = 1; j < dep - 1; j++) {
            if(check(b[j], b[j - 1], a[i], b[dep - 1])) { //与之前选的边有公共点 
                flag = false;
                break;
            }
        }
        if(flag) {
            vis[i] = true;
            b[dep] = a[i];
            dfs(dep + 1); //递归 
            vis[i] = false; //回溯 
        }
    }
}
signed main() {
    n = 1;
    cin >> a[n].x >> a[n].y;
    while(a[n].x || a[n].y) {
        ++n;
        cin >> a[n].x >> a[n].y;
    }
    dfs(1);
    cout << (ans >> 1) << endl;
    return 0;
}

AC 记录。