思路

首先,期望是线性的.

于是我们可以求出连接每一个农村所需长度的期望,然后全部加起来就OK了.

记 表示第 个城市, 表示第 个农村, 表示 与 相连的概率, 表示 与 的距离.

那么

现在我们依次处理每一个农村 .

先考虑城市的贡献.很明显只有离最近的城市才会有贡献.

对于与它最近的城市 ,如果更近的农村有个(不包括),那么与连接的概率为.

至于为什么,可以考虑所有农村的全排列(即连接的顺序),考虑其中更近的 个农村与 的相对位置,肯定是 在最前面,后面 个农村怎么排就没有关系了. 排在第 个,第 个...第 个的概率是相等的,因此排在最前面的概率就是 .(注意,这里说的第 个,第 个...仍然是这 个农村的相对位置)

更近的 个农村也有贡献.求法与上面类似,如果农村 是第 近的,那么 .

然后就可以愉快地求出答案了.

复杂度是 的(也就是说数据范围搞到 大概完全没问题).

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define f80 long double
#define rgt register
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline bool cmax( T &x, T y ){ return x < y ? x = y, 1 : 0; }
template<typename T> inline bool cmin( T &x, T y ){ return y < x ? x = y, 1 : 0; }

int N, M, n, w;
double ans;

struct node{ int x, y; }a[55], b[55];
struct D{
    double d; bool c;
    bool operator < ( const D &t )const{ return d < t.d; }
} c[105];

inline double sqr( double x ){ return x * x; }
inline double dist( node a, node b ){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}

signed main(){
    cin >> N >> M;
    fp( i, 1, N ) cin >> a[i].x; fp( i, 1, N ) cin >> a[i].y;
    fp( i, 1, M ) cin >> b[i].x; fp( i, 1, M ) cin >> b[i].y;
    fp( i, 1, M ){
        n = 0;
        fp( j, 1, N ) c[++n].d = dist(a[j], b[i]), c[n].c = 1;
        fp( j, 1, M ) if ( j != i ) c[++n].d = dist(b[j], b[i]), c[n].c = 0;
        sort( c + 1, c + n + 1 );
        fp( j, 1, n ) if ( c[j].c ){ ans += c[j].d / j; break; } else ans += c[j].d / (j * (j + 1));
    } printf( "%.10lf\n", ans );
    return 0;
}