P1153 点和线题解

b6e0_ · 2021-03-28 16:56:27 · 题解

题

题面的一个坑点是线段除端点外无交点而不是直线。

看到这 10 的数据范围，明显复杂度带有 n!。可以全排列做，但是为了方便剪枝，采用搜索。

枚举到一个排列 p，将 p_i 与 p_{i+1}（p_n 与 p_1）之间连线，主要任务就是判断任意两条线段之间是否有交点。

对于线段 AB 与 CD，它们之间有交点的充要条件是点 C 和 D 在直线 AB 的两侧且点 A 和 B 在直线 CD 的两侧。

考虑向量叉乘。若 \vec a\times\vec b>0，那么 \vec b 在 \vec a 的逆时针方向；若叉积小于 0，那么 \vec b 在 \vec a 的顺时针方向。于是，判断点 C 和 D 是否在直线 AB 的两侧，就是判断 \overrightarrow{AB}\times\overrightarrow{AC} 和 \overrightarrow{AB}\times\overrightarrow{AD} 是否同号。如果同号，那么在同侧；如果异号，那么在两侧。题目保证了任意三点不共线，所以叉积为 0 的情况不可能出现。判断点 A 和 B 在直线 CD 的两侧同理。时间复杂度 \mathcal O(n!n^2)，这个其实跑不满。代码：

#include<bits/stdc++.h>
using namespace std;
struct point
{
    double X,Y;
}a[15];
int p[15],n,ans;//p为选择的下标
bool cho[15];//cho表示是否已经选择
inline double cross(point x,point y)//叉积，这里向量也用point表示了，懒得开一个新的struct
{
    return x.X*y.Y-x.Y*y.X;
}
inline bool intersection(point x1,point y1,point x2,point y2)//判断是否有交点，有交点返回true
{
    double abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
    double abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
    if((abc>0&&abd>0)||(abc<0&&abd<0))
        return false;
    swap(x1,x2);
    swap(y1,y2);
    abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
    abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
    return ((abc>0&&abd<0)||(abc<0&&abd>0));
}
void dfs(int d)
{
    if(d>n)
    {
        int i;
        for(i=2;i<n-1;i++)
            if(intersection(a[p[n]],a[p[1]],a[p[i]],a[p[i+1]]))
                break;//第一个与最后一个连成的线段与其他是否有交点也要判断
        if(i==n-1)
            ans++;
        return;
    }
    for(int i=1;i<=n;i++)
        if(!cho[i])
        {
            int j;
            p[d]=i;
            for(j=1;j<d-2;j++)
                if(intersection(a[p[d-1]],a[p[d]],a[p[j]],a[p[j+1]]))
                    break;
            if(j>=d-2)
            {
                cho[i]=true;
                dfs(d+1);
                cho[i]=false;
            }
        }
}
int main()
{
    do
    {
        n++;
        cin>>a[n].X>>a[n].Y;
    }while(a[n].X!=0||a[n].Y!=0);
    dfs(1);
    cout<<ans/n/2;//一个多边形按照顺时针顺序有n个排列表示，逆时针也有n个，所以要除以2n
    return 0;
}

P1153 点和线 题解

P1153 点和线题解