JZOJ-senior-5917. 【NOIP2018模拟10.20】moon

本文主要是介绍JZOJ-senior-5917. 【NOIP2018模拟10.20】moon，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Time Limits: 2000 ms Memory Limits: 524288 KB

Description

作为申国的学者，你需要严格遵守三大基本原则：
战争即和平
自由即奴役
无知即力量
你正在对一本书进行审核，其中片段写道：
“少焉，月出于东山之上，徘徊于斗牛之间。白露横江，水光接天。纵一苇之所如，凌万顷之茫然。浩浩乎如冯虚御风，而不知其所止；飘飘乎如遗世独立，羽化而登仙。”
这种行为明显不符合三大原则，比如“纵一苇之所如”中自由的意思已经在新话中杯删除了。
但是你在修改的同时，发现书中夹着一道问题：
酥室等人现在的位置是(x,y)，同时还有n个景点，坐标分别为(xi,yi)。
每次移动按照下面的顺序操作：
1、选择一条直线，要求直线经过现在的位置和至少两个景点（如果现在在某个景点那里，也算一个）如果有多条直线满足要求，等概率选择一条。
2、在选择的这条直线中，等概率选择一个直线覆盖了的景点移动过去，如果目前在景点上，也有可能停住不动。
酥室会进行若干次询问，第i次询问从一个你选的任意点出发（可以不是景点），然后连续移动mi步，最后到达ti的最大概率是多少。

Input

第一行一个整数n。
接下来n行每行两个整数，表示xi,yi。
接下来一行一个整数m，表示询问数。
接下来m行每行两个整数ti,mi，表示询问。

Output

对于每个询问输出一行，表示最大的概率，与标准答案误差在10^-6以内就算正确。

Sample Input

5
0 0
1 3
2 2
3 1
4 4
10
1 1
2 1
3 1
4 1
5 1
3 2
3 3
3 4
3 5
3 6

Sample Output

0.50000000000000000000
0.50000000000000000000
0.33333333333333331483
0.50000000000000000000
0.50000000000000000000
0.18518518518518517491
0.15226337448559670862
0.14494741655235482414
0.14332164812274550414
0.14296036624949901017

Data Constraint

在这里插入图片描述

Solution

设 $p [i] [j]$ 为从 $i$ 走一步到 $j$ 的概率
所有经过 $i$ 的直线有 $c n t$ 条，其中，经过 $j$ 的那条直线上有 $n u m$ 个景点
那么 $p [i] [j] = 1 / c n t / n u m$

设 $a [x] [i] [j]$ 为 $i$ 走 $x$ 步到 $j$ 的概率
那么 $a[x][i][j]=\sum^{n}_{k=1}a[x-1][i][k]*p[k][j]$

如果每次询问都这么DP，那每次求解的复杂度为 $O（mi*n^3)$ ，不能通过此题

于是我们考虑优化这个求答案的过程

观察发现矩阵 $a [x]$ 的转化总是用 $a [x - 1]$ 的矩阵乘上概率矩阵 $p$ 得到，既然每次乘上的矩阵都相同，那我们可以使用矩阵乘法，先预处理出 $l o g$ 个矩阵，详见代码中的 $F [k] . a [i] [j]$ （表示从 $i$ 出发走 $2^k$ 步到 $j$ 的概率），这样的话，对于每次询问，就是一个 $1 * n$ 的矩阵（这个矩阵我们设为 $g$ ， $g [t] = 1$ ）和 $l o g$ 个 $n * n$ 的矩阵相乘，利用这种方法，我们倒着做，先求出从终点走 $m - 1$ 步到每个景点的概率（因为起点不一定在景点上，所以第一步不可以这么做），再处理第一步

对于第一步，它一定在某两点连成的直线上，但不在两直线的交点上
为什么呢？我们尝试这样理解
设起点为 $S$ ，平面内有两条直线 $L 1$ ， $L 2$ ，
直线上点的概率和以及总点数分别为 $s 1 ， s 2$ 和 $c 1 ， c 2$
从起点到终点的概率为 $P 2 ， P 2$
若 $S$ 在直线 $L 1$ 上且不在交点上，则 $P 1 = s 1 / c 1$
若 $S$ 在直线 $L 2$ 上且不在交点上，则 $P 2 = s 2 / c 2$
若 $S$ 在交点上，则 $P 3 = 1 / 2 * (s 1 / c 1 + s 2 / c 2)$
这样求出来的 $P 3$ 一定小于等于 $s 1 / c 1$ 或者 $s 2 / c 2$
换句话说就是不在交点上比在交点上的概率要大啦

Code

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define db doubleusing namespace std;const int N=210,M=1e4+5,inf=2147483647;
int n,m,en,cs,num,tot_k,_2[15];
db g[N],g1[N];
set<int> point[N*N];
set<int>::iterator it;
struct wz{int x,y;}pos[N];
struct matrix{db a[N][N];}F[15];
struct line{db k; int id;}K[N];
struct straight{db k,b;int x,y;}xl[N*N];bool cmp(line x,line y)
{return x.k<y.k||x.k==y.k&&x.id<y.id;
}bool cmq(straight x,straight y)
{return x.k<y.k||x.k==y.k&&x.b<y.b;
}matrix mul(matrix A,matrix B)
{matrix C;memset(C.a,0,sizeof(C.a));fo(i,1,n)fo(j,1,n)fo(k,1,n)C.a[i][j]+=A.a[i][k]*B.a[k][j];return C;
}int main()
{freopen("moon.in","r",stdin);freopen("moon.out","w",stdout);_2[0]=1;fo(i,1,14) _2[i]=_2[i-1]<<1;scanf("%d",&n);fo(i,1,n) scanf("%d%d",&pos[i].x,&pos[i].y);fo(i,1,n){int tot=0;fo(j,1,n) if(j!=i){int yy=pos[i].y-pos[j].y,xx=pos[i].x-pos[j].x;if(pos[i].x!=pos[j].x) K[++tot].k=(db)yy/xx;else K[++tot].k=inf;K[tot].id=j;xl[++tot_k]=(straight){K[tot].k,pos[i].y-K[tot].k*pos[i].x,i,j};}sort(K+1,K+1+tot,cmp);int cnt=0; K[n].k=-inf;fo(j,1,tot) if(K[j].k!=K[j+1].k) ++cnt;int lst=1;fo(j,1,tot) if(K[j].k!=K[j+1].k){int num=j-lst+1; ++num;F[0].a[i][i]+=1.0/cnt/num;fo(k,lst,j) F[0].a[i][K[k].id]=1.0/cnt/num;lst=j+1;}}fo(i,1,14) F[i]=mul(F[i-1],F[i-1]);sort(xl+1,xl+1+tot_k,cmq);xl[tot_k+1]=(straight){-inf,0,0};int lst=1,at=0;fo(i,1,tot_k) if(xl[i].k!=xl[i+1].k||xl[i].b!=xl[i+1].b){++at;fo(j,lst,i) point[at].insert(xl[j].x),point[at].insert(xl[j].y);lst=i+1;}scanf("%d",&m);fo(o,1,m){scanf("%d%d",&en,&cs),--cs;memset(g,0,sizeof(g));g[en]=1; fo(i,0,14) if(cs&_2[i]){memset(g1,0,sizeof(g1));fo(j,1,n)fo(k,1,n)g1[j]+=g[k]*F[i].a[j][k];memcpy(g,g1,sizeof(g));}db ans=0;fo(i,1,at){db sum=0;for(it=point[i].begin();it!=point[i].end();it++) sum+=g[*it];ans=max(ans,sum/point[i].size());}printf("%.10lf\n",ans);}
}