Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:128 MB

#2876. 阿黄游桃园新村(ayellow)

Statistics

黄太元中,南山人溜狗为业。缘溪行,忘路之远近。忽逢桃花林,夹岸数百步。中无杂树,芳草鲜美,落英缤纷,南山人甚异之。复前行,欲穷其林。林尽水源,便得一山,山有小口,仿佛仅狗可入。阿黄便舍主,从口入。遂迷,不复得路。南山ZGY,高尚士也,闻之,欣然规往。见阿黄,曰:“吾上通天文,下知地理,期间以善游迷宫为最。吾有闻,出迷宫者可知新村桃园安在。”黄闻之,遂狂吠不止。ZGY笑曰“如要成此事,汝须助吾。”吠曰:“何事之有?”。 众所共知,ZGY嗜真知棒。而ZGY给了阿黄n点。此n点上有ZGY须之真知棒,使阿黄中求出一个周最短之多边形,众点俱在其中,后ZGY持了多边形上之有真知棒,又令阿黄自求出多边形者每一边之情一点发,使阿黄求出取不在多边形上之最近者一知棒之最少之路。可惜阿黄上语文课的时候在睡觉,根本不知道ZGY在崩些什么,于是阿黄找到了你,作为上课不睡觉的你,一眼就看出他是让你对于每条边,求不在多边形上的点到这条边所在直线的最短距离。 俄而黄忽觉豁然开朗。土地平旷,屋舍俨然,有良田美池桑竹之属。阡陌交通,鸡犬相闻。其中往来种作,女生衣着,悉如仙子。班姬续史之姿,谢庭咏雪之态.增之一分则太长,减之一分则太短。

见阿黄来,乃大惊,问所从来。具答之。便要还家,设酒杀鸡作食。村中闻有阿黄,咸来问讯。自云先世避NOIP之乱,众姐妹来此绝境,不复出焉,遂与外人间隔。问今是何世,乃不知有SCOI,无论APIO、NOI。阿黄一一为具言所闻,皆叹惋。余人各复延至其家,皆出酒食。停数日,辞去。此中人语云:“不足为外人道也。” 阿黄喜极而归之。

【输入格式】

输入第一行为一个数字n,表示有n个点。

接下来n行,第i+1行表示第i个点的横纵坐标

【输出格式】

输出共n行,每一行一个数字,由小到大输出某条边求出的答案值。

【输入样例】

10
6 21
20 13
17 19
15 5
15 7
13 7
5 13
5 21
9 17
20 8

【输出样例】

0.312348
1.714986
3.398823
4.000000
4.000000
5.000000
7.155418

【数据范围与约定】

对于20%的数据,有n<=300,

对于50%的数据,有n<=50000,

对于100%的数据,有n<=100000。

对于你的输出和标准答案,只要误差不超过0.0001,我们都认为是正确的,数据保证有解。