Wuyanru's blog
0%

[QOJ5443] Security at Museums

发表于 分类于 ，

很多细节的几何题。

题目链接。

题意

现在有一个 个点的简单多边形，顶点按照逆时针方向给出。

称一对点是好的，当且仅当这对点的连线没有经过多边形外的区域。

问有多少个大小 的点集，使得其中每对点都是好的。

。

题解

先考虑如何判断一对点合不合法。

首先，如果这对点直接的连线与多边形的某条边严格相交了，那一定是不合法的。

除此之外，还有整条线段全在多边形外面的情况，这种可以转出极坐标角度瞎判一判。

问题主要在于，这对点中间如果有另外一个点共线的情况，比较麻烦。

稍作思考可以发现，如果 中间有一个点 ，那么连线 合法当且仅当 都合法。

所以对于共线的情况，只需要跑一个类似 Floyd 的东西就好了。

这样我们就在 的复杂度内判出来每一对点合不合法。

现在考虑如何计数，观察一个合法方案对应点集的凸包。

可以发现，如果这是一个合法点集，那么凸包上相邻两个点的连线一定都在多边形内，这说明凸包内部（不包括凸包上）应该不能有别的点。

也就是说，一个合法点集的所有点应当构成了一个凸包。同时，只需要凸包上相邻两点连线合法，这个点集就合法。

那么这样就可以考虑计数了。

枚举整个凸包中纵坐标最小的点（一样则要求横坐标最小），考虑计算凸包的数量。

将所有合法的连线按照极角序进行排序，然后对凸包进行 dp 就行了。

使用 表示当前走到 的方案数，然后按照上面排序好的连线顺序进行转移。

这里因为有三点共线，所以可能会出现一条直线上来回走的情况，需要特殊处理，但是这并不复杂。

时间复杂度 。

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=998244353;
struct node
{
    int u,v;
    ld x,y;
}a[40001];
bool e[201][201];
bool vis[201];
int id[201];
ll dp[201][2];
ld x[201];
ld y[201];
int n,c;
inline bool type(int x,int y)
{
    if(y>0) return 0;
    if(y<0) return 1;
    return x<0;
}
inline ld cha(int a,int b,int c)
{
    return (x[b]-x[a])*(y[c]-y[a])-(y[b]-y[a])*(x[c]-x[a]);
}
inline bool xian(int a,int b,int c)
{
    if((x[a]>x[b])!=(x[b]>x[c])) return false;
    if((y[a]>y[b])!=(y[b]>y[c])) return false;
    return cha(a,b,c)==0;
}
inline bool ins(int a,int b,int u,int v)
{
    ld v1=cha(a,b,u),v2=cha(a,b,v);
    ld v3=cha(u,v,a),v4=cha(u,v,b);
    if(!v1||!v2||!v3||!v4) return false;
    return (v1>0)!=(v2>0)&&(v3>0)!=(v4>0);
}
inline ld dis(int a,int b)
{
    return sqrtl((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
inline ld get(int a,int b)
{
    ld C=(x[b]-x[a])/dis(a,b),ans=acos(C);
    if(y[a]<y[b]||(y[a]==y[b]&&x[b]>x[a])) return ans;
    return 2*acos(-1)-ans;
}
inline void Add(ll &a,ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
inline ll run(int id)
{
    memset(dp,0,sizeof(dp));ll ans=0;
    for(int i=1;i<=c;i++)
    {
        if(vis[a[i].u]||vis[a[i].v]) continue;
        if(a[i].u==id) Add(dp[a[i].v][0],1),Add(ans,1);
        else if(a[i].v==id) Add(ans,dp[a[i].u][1]);
        else if(xian(id,a[i].u,a[i].v)) Add(ans,dp[a[i].u][0]),Add(dp[a[i].v][0],dp[a[i].u][0]);
        else if(xian(id,a[i].v,a[i].u)) Add(dp[a[i].v][0],dp[a[i].u][0]),Add(dp[a[i].v][1],dp[a[i].u][1]);
        else Add(dp[a[i].v][1],dp[a[i].u][0]),Add(dp[a[i].v][1],dp[a[i].u][1]);
    }
    vis[id]=1;
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)
    {
        if(i%n+1==j||j%n+1==i){ e[i][j]=1;continue;}
        bool f=1;
        for(int k=1;k<=n;k++)
        {
            if(k==i||k%n+1==i) continue;
            if(k==j||k%n+1==j) continue;
            if(ins(i,j,k,k%n+1)) f=0;
        }
        if(!f) continue;
        int lt=(i+n-2)%n+1,nx=i%n+1;
        if(xian(i,lt,j)||xian(i,nx,j)){ e[i][j]=1;continue;}
        ld v1=get(i,lt),v2=get(i,j),v3=get(i,nx);
        if(v2<v3) v2+=2*acos(-1);
        if(v1<v3) v1+=2*acos(-1);
        if(v2<v1) e[i][j]=1;
    }
    for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) for(int k=1;k<=n;k++)
        if(i!=j&&j!=k&&i!=k&&xian(i,j,k)&&(!e[i][j]||!e[j][k])) e[i][k]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&!e[i][j])
    {
        int lt=(i+n-2)%n+1,nx=i%n+1;
        if(xian(i,lt,j)) e[i][j]=e[lt][j];
        if(xian(i,nx,j)) e[i][j]=e[nx][j];
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j])
    {
        c++;
        a[c].u=i,a[c].v=j;
        a[c].x=x[j]-x[i],a[c].y=y[j]-y[i];
    }
    sort(a+1,a+c+1,[](node a,node b) -> bool
    {
        bool v1=type(a.x,a.y),v2=type(b.x,b.y);
        if(v1!=v2) return v1<v2;
        ld p=a.x*b.y-a.y*b.x;
        if(p) return p>0;
        if(y[a.u]!=y[b.u]) return (y[a.u]<y[b.u])^v1;
        return (x[a.u]<x[b.u])^v1;
    });

    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,[](int a,int b)
    {
        if(y[a]!=y[b]) return y[a]<y[b];
        return x[a]<x[b];
    });

    ll ans=0;
    for(int i=1;i<=n;i++) ans+=run(id[i]);
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}