Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:64 MB

#1392. 国王的一周

统计


Description
  从前有一个国王,他有一片很大的领地。每天他都要处理很多的事情,以下便是国王的工作日。
  星期一,国王想要建一座环绕他的领地的围墙,国王的领地是由许多村落组成的,这些围墙必须与任意一个村落保持至少R米的距离,由于国库紧缺,国王想知道在最节省材料的情况下,这个围墙有多长。
  星期二,国王要去邻国访问,上午他要去邻国的A村开会,下午他要去B村开会。邻国是一个注重清洁的国家,清洁到国家中没有人开汽车,全部骑自行车!国王也只好骑自行车往来A,B两村。但是国王开会已经很累了,他迫切地想知道他可能骑车的最长距离,以便提前做好准备。(开会的地点是由邻国的国王决定的,国王并不知道,所以国王只能假设A、B村可能是任何一个村落)
  星期三,喵星人攻打过来了!他们在笛卡尔坐标系中开着“整齐”的舰队(至少在喵星人看来是很整齐的,因为每个舰队的相对位置都是不变的)。幸好国王的科学家ZGL为国王发明了激光武器来对抗喵星人。激光武器有很大的口径(你可以认为有十几公里),因此利用激光可以一次将舰队口径范围内的舰队扫除。国王想一次消灭整个舰队以防后患,但使用激光的费用是高昂的,国王不得不考虑用最小的口径来消灭舰队。(激光口径可以无限大,也可以无限小[此时输出0.00])
2013121619545075357.jpg
  星期四,由于国王的国土辽阔,他一直不清楚自己的领土有多大。今天,他在研究自己的领土,发现自己的领土在边界上居然和领国重合了!后来他发现周边的多个国家都有这个现象(领土重合)。好奇的他想知道是否有一块土地属于所有的国家,它的面积是多少?(为了方便处理,假设所有国家的领土都是凸多边形)。
  星期五,国王要召开会议(又是开会!),开会区域由一个凸多边形组成(又是凸多边形!)。为了会议安全,开会期间需要有人巡视,幸好科学家ZGL(又是ZGL!)发明了一个机器人来帮助解决这个问题。由于在仓促间制作,机器人有不少缺陷(它只有左眼睛[即机器人任意时刻只能看到左边的一半],它只能直走或左转90°)。机器人需要不停的围绕会场巡视,要求它在巡视的任意时刻都能完整地看到整个会场。由于能源危机,国王希望机器人绕一圈所走的长度最短。


Input
  多组数据,每组数据先一个整数T(T=0表示结束),表示今天是星期几,你需要根据不同的日子帮助国王做不同的事情:
  星期一:第一行两个数N,R。N表示村落个数,接下来每个N个坐标表示村庄。
  星期二:第一行一个数N,表示村落个数,接下来每个N个坐标表示村庄。
  星期三:第一行一个数N,表示舰队个数,接下来每个N个坐标表示舰队。
  星期四:第一行一个数M,表示邻国的个数,接下来描述M+1个国家,每个国家第一行一个数N,接下来逆时针N个坐标描述每个顶点。
  星期五:描述一个会场,描述方法同上。
  保证数据合法,没有重复的点


Output
   对于不同的日子你需要输出对应的答案,具体来说你要输出:
  星期一:围墙长度
  星期二:国王骑车距离
  星期三:激光口径
  星期四:第一行YES或NO表示是否存在这样的土地,如果存在第二行输出面积
  星期五:机器人走一圈的长度。
  所有输出保留2位小数(答案与标准答案误差不超过0.01)


20131216195523947256.jpg


样例输入(这里为了方便阅读每组输入之间用回车隔开了,在测试时每组输入之间没有回车)
1
4 1
0 0
1 0
1 1
0 1


2
4
0 0
1 0
1 1
0 1


3
4
0 0
1 0
1 1
0 1


4
1
3
0 0
2 0
0 2
3
0 0
2 2
0 2


5
3
0 0
1 0
0 1


0


样例输出
10.28
1.41
1.00
YES
1.00
4.00


提示:计算几何在计算中会有精度误差,因此对于两个相对差值在1e-6内的数我们视作相同。