理想国

时间限制：10s 空间限制：256MB

题目描述

问题描述
　　上帝永远将一切几何化。——柏拉图

　　功成名就的金先生开始研究起哲学来了。他做了一个梦，梦见他拥有了一个理想国！
　　他的理想国山明水秀，风光旖旎。城市繁荣，交通发达。土地平旷，屋舍俨然，有桑竹美池良田之属，阡陌交通，鸡犬相闻。
　　把理想国的城市标号为1至n，每个城市有一个独立的编号。在地图上，可以建立一个平面直角坐标系，用一个坐标表示一座城市的位置。一些城市间修建了笔直的高速公路。公路一共有m条。为了避免相撞事故，除端点外，任两条公路没有公共点。理想国的城市是双连通的，亦即任何两个城市间可以找到两条不相交的简单路径。
　　金先生的理想国的每个城市的繁荣程度不同，最繁荣的繁荣度为1,最破败的繁荣度为n。一条公路两端的城市的繁荣度如果分别为a和b(a < b)，那么称开区间(a, b)为这条公路的特征区间。观察两条公路，它们的路况相似，当且仅当它们的特征区间的交非空。
　　金先生一觉醒来，只记得理想国城市布局，而忘了城市的繁荣情况了。于是，他想解决下面两个问题。
　　(1) 平均情况下，相似的路有几对？
　　(2) 最好情况下，最多能有几条路，它们两两相似？

输入格式

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

输出格式

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

样例输入

样例输出

2.000 2

提示

数据规模和约定
　　对10%的数据，n <= 9。
　　对20%的数据，n <= 13。
　　另有30%的数据，布局分别为简单多边形，网格图，三角形带。
　　另有10%的数据，包含不超过10行，每行全是正方形或三角形，每个正方形行的正方形个数不超过10，每个三角形行的三角形个数不超过20。
　　另有10%的数据，包含不超过13个面。
　　对于100%的数据，n <= 100，坐标绝对值在30000以内。我们约定，三角形带为形如下图所示的形状。其中，它的一组平行边平行于坐标轴。不仅如此，网格图的边也平行于坐标轴。

题目来源

By 佚名提供