洛谷P7529 Permutation G

传送门

题目描述

Bessie 在二维平面上有 NN 个最爱的不同的点，其中任意三点均不共线。对于每一个 1\le i\le N1≤i≤N，第 ii 个点可以用两个整数 x_ix
i
​
和 y_iy
i
​
表示。

Bessie 按如下方式在这些点之间画一些线段：

她选择这 NN 个点的某个排列 p_1,p_2,\dots,p_Np
1
​
,p
2
​
,…,p
N
​
。
她在点 p_1p
1
​
和 p_2p
2
​
、p_2p
2
​
和 p_3p
3
​
、p_3p
3
​
和 p_1p
1
​
之间画上线段。
然后依次对于从 44 到 NN 的每个整数 ii，对于所有 j i
​
到 p_jp
j
​
画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。
Bessie 注意到对于每一个 ii ，她都画上了恰好三条新的线段。计算 Bessie 在第 11 步可以选择的满足上述性质的排列的数量，结果对 10^9+710
9
+7 取模。

输入格式

输入的第一行包含 NN。

以下 NN 行，每行包含两个空格分隔的整数 x_ix
i
​
和 y_iy
i
​
。

输出格式

输出一行一个整数表示方案数对 10^9+710
9
+7 取模后的结果。

输入输出样例

洛谷【LGR-(-11)】CSP 2020 第一轮（初赛）模拟

pdf 0星 超过10%的资源 3.98MB

下载

输入 #1复制
4
0 0
0 4
1 1
1 2
输出 #1复制
0
输入 #2复制
4
0 0
0 4
4 0
1 1
输出 #2复制
24
输入 #3复制
5
0 0
0 4
4 0
1 1
1 2
输出 #3复制
96

说明/提示

样例一解释
没有排列满足该性质

样例二解释
所有排列均满足该性质

样例解释三
一个满足该性质的排列为 (0,0),(0,4),(4,0),(1,2),(1,1)(0,0),(0,4),(4,0),(1,2),(1,1) 。对于这个排列，

首先，她在 (0,0),(0,4)(0,0),(0,4) 和 (4,0)(4,0) 两两之间画上线段。
然后她从 (1,2)(1,2) 向 (0,0)(0,0) ，(0,4)(0,4) 和 (4,0)(4,0) 画上线段。
最后，她从 (1,1)(1,1) 向 (1,2)(1,2) ，(4,0)(4,0) 和 (0,0)(0,0) 画上线段。

数据范围与约定

3\le N \le 403≤N≤40，0\le x_i,y_i \le 10^40≤x
i
​
,y
i
​
≤10
4

上代码：

#include
#define ll long long
#define pb push_back
#define mid ((l+r)>>1)
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
using namespace std;
bool hasinon;
ll time1=clock();
//
struct node{
	ll x,y;
};
const ll N=40,MOD=1e9+7;
node zb[N+10];
ll stac[5],lstac[5]; 
ll dp[N+10][N+10][N+10][N+10],hav[N+10][N+10][N+10];
//
inline ll cj(node a,node b){
//	printf("%lld %lld %lld %lld\n",a.x,a.y,b.x,b.y) ;
	return a.x*b.y-b.x*a.y;
}
ll ksm(ll a,ll b){
	ll rt=1,la=a;
	while(b){
		if(b&1) rt=rt*la%MOD;
		la=la*la%MOD;
		b>>=1;
	}
	return rt;
}
//
bool Hasinon;
void usage() {
	ll time2=clock();
	cout<<(&Hasinon-&hasinon)/1024/1024<<" Mb, "<<time2-time1<<" Ms\n";
}
int main() {
	ll n=gt();
	FOR(i,1,n){
		zb[i]=(node){gt(),gt()};
	}
	FOR(i,1,n){
		FOR(j,i+1,n){
			FOR(k,j+1,n){
				dp[i][j][k][3]=6;
			}
		}
	}
	FOR(c,3,n-1){
		FOR(i,1,n){
			stac[1]=i;
			FOR(j,i+1,n){
				stac[2]=j;
				FOR(k,j+1,n){
					stac[3]=k;
					if(!dp[i][j][k][c]) continue; 
					if(c>3&&hav[i][j][k]){
						dp[i][j][k][c+1]=(dp[i][j][k][c+1]+dp[i][j][k][c]*(hav[i][j][k]-c+3))%MOD;
					}
					FOR(l,1,n){
						bool lb=0;
						FOR(m,1,3){
							if(l==stac[m]){
								lb=1; break;
							}
						}
						if(lb) continue;
						double stot=abs(cj((node){zb[i].x-zb[l].x,zb[i].y-zb[l].y},(node){zb[j].x-zb[l].x,zb[j].y-zb[l].y}))+
						abs(cj((node){zb[j].x-zb[l].x,zb[j].y-zb[l].y},(node){zb[k].x-zb[l].x,zb[k].y-zb[l].y}))+
						abs(cj((node){zb[k].x-zb[l].x,zb[k].y-zb[l].y},(node){zb[i].x-zb[l].x,zb[i].y-zb[l].y}));
						stot/=2;
						double stri=abs(cj((node){zb[j].x-zb[i].x,zb[j].y-zb[i].y},(node){zb[k].x-zb[i].x,zb[k].y-zb[i].y}));
						stri/=2;
						if(stot==stri){
							if(c==3){
								++hav[i][j][k];
								dp[i][j][k][c+1]+=dp[i][j][k][c];
								dp[i][j][k][c+1]%=MOD;
							}
							continue;
						}
						ll to1,to2;
						FOR(mmto,1,3){
							if(mmto==1) to1=2,to2=3;
							if(mmto==2) to1=1,to2=3;
							if(mmto==3) to1=1,to2=2;
							ll t1=cj((node){zb[stac[mmto]].x-zb[l].x,zb[stac[mmto]].y-zb[l].y},(node){zb[stac[to1]].x-zb[l].x,zb[stac[to1]].y-zb[l].y});
							ll t2=cj((node){zb[stac[mmto]].x-zb[l].x,zb[stac[mmto]].y-zb[l].y},(node){zb[stac[to2]].x-zb[l].x,zb[stac[to2]].y-zb[l].y});
							ll t3=cj((node){zb[stac[to1]].x-zb[stac[to2]].x,zb[stac[to1]].y-zb[stac[to2]].y},(node){zb[stac[to1]].x-zb[l].x,zb[stac[to1]].y-zb[l].y});
							ll t4=cj((node){zb[stac[to1]].x-zb[stac[to2]].x,zb[stac[to1]].y-zb[stac[to2]].y},(node){zb[stac[to1]].x-zb[stac[mmto]].x,zb[stac[to1]].y-zb[stac[mmto]].y});
							if(t1*t2<0&&t3*t4>0){
								FOR(m,1,3) lstac[m]=stac[m];
								lstac[mmto]=l;
								sort(lstac+1,lstac+4);
								dp[lstac[1]][lstac[2]][lstac[3]][c+1]+=dp[i][j][k][c];
								dp[lstac[1]][lstac[2]][lstac[3]][c+1]%=MOD;
								break;
							}	
						}
						
					}
				}
			}
		}
	}
	ll ans=0;
	FOR(i,1,n){
		FOR(j,i+1,n) {
			FOR(k,j+1,n){
				if(!dp[i][j][k][n]) continue; 
				ans+=dp[i][j][k][n];
			}
		}
	}
	printf("%lld",ans);
}
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