果然 YL 国的 DP 都是码农 DP……
首先按照 \(x\) 坐标排序忽略掉一些影响，\(O(n^2)\) 预处理每个点向四个方向作射线是否会碰到其他点。
DP 时，既然点的影响已经解决了，那么问题在于射线的影响。
可以在状态记录以下四个值： 1. 最右边的向左的射线。 2. 最左边的向右的射线。 3. 最左边的向下的射线。 4. 最右边的向下的射线。
这样，
向上，判断是否与 \(1,2\) 相交并转移；
向左，判断是否与 \(3\) 相交，更新 \(1\) 并转移；
向右，判断是否与 \(4\) 相交，更新 \(2\) 并转移；
向下，更新 \(3,4\) 并转移。
然后第一维要滚动。
代码： 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
using namespace std;
const int N = 54;
const long long mod = 998244353;
int n;
struct note
{
int x,y;
inline bool operator<(const note &o) const
{
return x < o.x || (x == o.x && y < o.y);
}
} a[N + 5];
long long f[2][N + 5][N + 5][N + 5][N + 5],ans;
int p[N + 5][4];
int mx(int x,int y)
{
return !x ? y : (a[x].y < a[y].y ? y : x);
}
int mn(int x,int y)
{
return !x ? y : (a[x].y > a[y].y ? y : x);
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a + 1,a + n + 1);
for(register int i = 1;i <= n;++i)
for(register int j = 0;j < 4 && (p[i][j] = 1);++j)
for(register int k = 1;k <= n;++k)
if(i ^ k)
{
if(j == 0 && a[i].x == a[k].x && a[i].y < a[k].y)
p[i][j] = 0;
if(j == 1 && a[i].x == a[k].x && a[i].y > a[k].y)
p[i][j] = 0;
if(j == 2 && a[i].y == a[k].y && a[i].x > a[k].x)
p[i][j] = 0;
if(j == 3 && a[i].y == a[k].y && a[i].x < a[k].x)
p[i][j] = 0;
if(!p[i][j])
break;
}
int x = 0,y = 1;
f[0][0][0][0][0] = 1;
for(register int i = 0;i < n;++i,x ^= 1,y ^= 1)
{
for(register int s = 0;s <= i;++s)
for(register int t = 0;t <= i;++t)
for(register int u = 0;u <= i;++u)
for(register int v = 0;v <= i;++v)
f[y][s][t][u][v] = 0;
for(register int s = 0;s <= i;++s)
for(register int t = 0;t <= i;++t)
for(register int u = 0;u <= i;++u)
for(register int v = 0;v <= i;++v)
{
if(!f[x][s][t][u][v])
continue;
if(((a[s].y < a[i + 1].y && a[t].y > a[i + 1].y) || (!s && a[t].y > a[i + 1].y) || (a[s].y < a[i + 1].y && !t) || (!s && !t)) && p[i + 1][2])
(f[y][s][t][u][v] += f[x][s][t][u][v]) %= mod;
if(((a[u].y > a[i + 1].y) || !u) && p[i + 1][1])
(f[y][mx(s,i + 1)][t][u][v] += f[x][s][t][u][v]) %= mod;
if(((a[v].y < a[i + 1].y) || !v) && p[i + 1][0])
(f[y][s][mn(t,i + 1)][u][v] += f[x][s][t][u][v]) %= mod;
if(p[i + 1][3])
(f[y][s][t][mn(u,i + 1)][mx(v,i + 1)] += f[x][s][t][u][v]) %= mod;
}
}
for(register int s = 0;s <= n;++s)
for(register int t = 0;t <= n;++t)
for(register int u = 0;u <= n;++u)
for(register int v = 0;v <= n;++v)
(ans += f[x][s][t][u][v]) %= mod;
printf("%lld\n",ans);
}