#P3584. 理想国

    ID: 2785 传统题 1000ms 256MiB 尝试: 4 已通过: 2 难度: 10 上传者: 标签>难度分类省选/NOI-概率与期望指示变量期望线性性图论平面图对偶半边面遍历计算几何叉积构造与建模奇偶性分析Floyd–WarshallBlossom 算法最小权 T-joinCF2900By佚名提供

理想国

理想国

题目描述

上帝永远将一切几何化。——柏拉图

功成名就的金先生开始研究起哲学来了。他做了一个梦,梦见他拥有了一个理想国! 他的理想国山明水秀,风光旖旎。城市繁荣,交通发达。土地平旷,屋舍俨然,有桑竹美池良田之属,阡陌交通,鸡犬相闻。

把理想国的城市标号为 11 至 nn,每个城市有一个独立的编号。在地图上,可以建立一个平面直角坐标系,用一个坐标表示一座城市的位置。一些城市间修建了笔直的高速公路,公路一共有 mm 条。为了避免相撞事故,除端点外,任两条公路没有公共点。理想国的城市是双连通的,亦即任意两个城市间存在两条除起点、终点外不共用城市的简单路径。

金先生的理想国的每个城市的繁荣程度不同,最繁荣的繁荣度为 11,最破败的繁荣度为 nn。一条公路两端的城市的繁荣度如果分别为 aa 和 bb(a<ba<b),那么称开区间 (a,b)(a,b) 为这条公路的特征区间。观察两条公路,它们的路况相似,当且仅当它们的特征区间的交非空。

金先生一觉醒来,只记得理想国城市布局,而忘了城市的繁荣情况了。于是,他想解决下面两个问题。

  1. 将 11 至 nn 的繁荣度等概率地分配给 nn 座城市,相似公路对数的期望是多少?

  2. 在所有繁荣度分配中,最多能选出多少条两两相似的公路?

输入格式

第一行两个整数 n,mn,m,代表城市数和公路数。
接下来 nn 行,每行两个整数,代表标号为 ii 的城市在地图上的坐标。
接下来 mm 行,每行两个整数,为一条公路连接的两个城市的编号。

输出格式

仅一行,用空格分开,表示两小问的答案。第一问的答案保留小数点后 33 位。

样例

3 3
1 9
2 8
0 0
1 2
2 3
3 1
2.000 2

数据规模与约定

对 10%10\% 的数据,n≤9n\le 9。
对 20%20\% 的数据,n≤13n\le 13。
另有 30%30\% 的数据,布局分别为简单多边形,网格图,三角形带。
另有 10%10\% 的数据,包含不超过 1010 行,每行全是正方形或三角形,每个正方形行的正方形个数不超过 1010,每个三角形行的三角形个数不超过 2020。
另有 10%10\% 的数据,包含不超过 1313 个面。

对于 100%100\% 的数据,n≤100n\le 100,坐标绝对值在 3×1043\times 10^4 以内。三角形带的一组平行边平行于坐标轴;网格图的边也平行于坐标轴。下图根据正式数据中的一组三角形带的城市坐标和公路绘制,纵向比例放大,便于查看路网。

三角形带的正式数据示例