P1153 点和线网页链接P1153 点和线题目描述平面上有一些点你可以用直线将两点连接起来。那么有多少种方法可以把这些点连续地连起来使得任何两个线都不交叉。显然三个点只有一种方法。四个点最多只有3 33种方法。写一个程序计算方法总数。输入格式每一行是一个点的坐标坐标值是整数中间用一个空格隔开。最后一个坐标是原点。任意三点不在一条直线上。输出格式输出方案总数。输入输出样例 #1输入 #1100 -10 -200 0 45 7 0 0输出 #13说明/提示最多只有10 1010个点。必须从一个点出发途径所有点回到起点的路径才会被统计。两个方案不相同当且仅当围成的简单多边形不同。解题思路本题是搜索 剪枝 叉积判相交的问题。给定最多10 1010个平面点要求统计以这些点为顶点的简单多边形即相邻边不相交首尾相连的方案总数且两个方案只有在围成的多边形不同时才视为不同。由于点数很少可以采用 DFS 枚举所有点的连接顺序并在构造过程中判断当前边是否与已构造边相交剪枝无效搜索。1. 问题等价转化路径要求从一个点出发依次经过所有其他点一次最后回到起点形成一个闭合多边形且任意两条边不能相交包括不相邻的边。方案去重由于没有指定起点但多边形由顶点顺序决定。若固定起点为某个点如代码固定为1 11号点枚举其余点的排列则每个多边形会被枚举两次顺时针和逆时针因此最终答案需除以2 22。2. 线段相交判定使用向量叉积判断线段A B ABAB与C D CDCD是否严格相交端点重合不算相交因为相邻边共享端点题目保证任意三点不共线。若同时满足cross ⁡ ( C , D , A ) × cross ⁡ ( C , D , B ) 0 \operatorname{cross}(C,D,A)\times \operatorname{cross}(C,D,B) 0cross(C,D,A)×cross(C,D,B)0且cross ⁡ ( A , B , C ) × cross ⁡ ( A , B , D ) 0 \operatorname{cross}(A,B,C)\times \operatorname{cross}(A,B,D) 0cross(A,B,C)×cross(A,B,D)0则说明两条线段在内部相交交叉。3. DFS 构造与剪枝输入与初始化读入所有点直到遇到原点( 0 , 0 ) (0,0)(0,0)。有效点数量为n nn其中原点也是有效顶点。固定起点令v [ 1 ] 1 v[1]1v[1]1从第二个顶点开始搜索。DFS 过程dfs(step)当step n1时表示已排列完所有点此时还需检查最后一条从v [ n ] v[n]v[n]回到v [ 1 ] v[1]v[1]的边是否与已有边相交。若合法则ans。否则枚举未使用的点i ii2 ≤ i ≤ n 2 \le i \le n2≤i≤n调用ok(step, i)判断将i ii作为第s t e p stepstep个顶点时新边v [ s t e p − 1 ] → i v[step-1] \to iv[step−1]→i是否与之前已构造的边除了与它相邻的最后一条边相交。若不交叉则递归。ok(step, nxt)函数检查新边与已构造边v [ i − 1 ] → v [ i ] v[i-1]\to v[i]v[i−1]→v[i]i 2 ∼ s t e p − 2 i2 \sim step-2i2∼step−2是否相交。由于相邻边只共享端点不检查最后一段v [ s t e p − 2 ] → v [ s t e p − 1 ] v[step-2]\to v[step-1]v[step−2]→v[step−1]因为它是新边的邻边。4. 复杂度分析时间复杂度最多10 1010个点固定起点后最多枚举9 ! 9!9!种排列且有剪枝实际搜索空间极小足以通过。空间复杂度O ( n ) O(n)O(n)存储点的坐标、访问标记和当前路径。总结本题本质上是在全排列搜索中逐步构造闭合多边形利用叉积判断当前边与已有边是否相交及时剪枝。最后将得到的路径数除以2 22得到不同多边形的数量。该方法简单直接适合点数很小的情况。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structP{doublex,y;}p[20];ll n1,ans;ll v[20];boolvis[20];doublecross(P a,P b,P c){return(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}boolintersect(P a,P b,P c,P d){returncross(c,d,a)*cross(c,d,b)0cross(a,b,c)*cross(a,b,d)0;}boolok(ll step,ll nxt){for(ll i2;istep-1;i){if(intersect(p[v[i-1]],p[v[i]],p[v[step-1]],p[nxt]))returnfalse;}returntrue;}voiddfs(ll step){if(stepn1){if(ok(step,1))ans;return;}for(ll i2;in;i){if(!vis[i]ok(step,i)){vis[i]1;v[step]i;dfs(step1);vis[i]0;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(true){cinp[n].xp[n].y;if(p[n].x||p[n].y)n;elsebreak;}v[1]1;dfs(2);coutans/2endl;return0;}