http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1512. 理想国
时间限制:1.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
上帝永远将一切几何化。——柏拉图

功成名就的金先生开始研究起哲学来了。他做了一个梦,梦见他拥有了一个理想国!
他的理想国山明水秀,风光旖旎。城市繁荣,交通发达。土地平旷,屋舍俨然,有桑竹美池良田之属,阡陌交通,鸡犬相闻。
把理想国的城市标号为1至n,每个城市有一个独立的编号。在地图上,可以建立一个平面直角坐标系,用一个坐标表示一座城市的位置。一些城市间修建了笔直的高速公路。公路一共有m条。为了避免相撞事故,除端点外,任两条公路没有公共点。理想国的城市是双连通的,亦即任何两个城市间可以找到两条不相交的简单路径。
金先生的理想国的每个城市的繁荣程度不同,最繁荣的繁荣度为1,最破败的繁荣度为n。一条公路两端的城市的繁荣度如果分别为a和b(a < b),那么称开区间(a, b)为这条公路的特征区间。观察两条公路,它们的路况相似,当且仅当它们的特征区间的交非空。
金先生一觉醒来,只记得理想国城市布局,而忘了城市的繁荣情况了。于是,他想解决下面两个问题。
(1) 平均情况下,相似的路有几对?
(2) 最好情况下,最多能有几条路,它们两两相似?
输入格式
第一行两个整数n, m,代表城市数和公路数。
接下来n行,每行两个整数,代表标号为i的城市在地图上的坐标。
接下来m行,每行两个整数,为一条公路连接的两个城市的编号。
输出格式
仅一行,用空格分开,表示两小问的答案。第一问的答案保留小数点后3位。
样例输入
3 3
1 9
2 8
0 0
1 2
2 3
3 1
样例输出
2.000 2
数据规模和约定
对10%的数据,n <= 9。
对20%的数据,n <= 13。
另有30%的数据,布局分别为简单多边形,网格图,三角形带。
另有10%的数据,包含不超过10行,每行全是正方形或三角形,每个正方形行的正方形个数不超过10,每个三角形行的三角形个数不超过20。
另有10%的数据,包含不超过13个面。
对于100%的数据,n <= 100,坐标绝对值在30000以内。我们约定,三角形带为形如下图所示的形状。其中,它的一组平行边平行于坐标轴。不仅如此,网格图的边也平行于坐标轴。