PID31 / [stupid]愚蠢的村庄
题目描述

背景

Stupid家族的成员们生活在一个名为Stupid的村庄。

话说村里的人要喝水都得到很远很远的另一个Genius村庄打水,这并不算什么,因为Stupid村庄的村民都很勤劳不怕苦。最郁闷的是Genius村庄的村民总是无端BS我们的村民,老是问一些“1+1等于多少”的问题,害得我们答不上来。于是hyc提出要在我们自己村里建一口水井。抛开受BS的日子。

描述

Stupid村庄的村民是愚蠢的,这个村庄也是愚蠢的,他们不知道如何布置自己的村庄,所以村庄的结构很简单。我们设整个村庄处在一个坐标系的第一象限。

而在Stupid村庄里有N座房子,这房子也是愚蠢的。它很扁,可以近似得看做一条直线;它还是平行于坐标轴的(Stupid村民是迷信的…方方正正才是美…)。

现在,要在村里建一水井,我们要使所有房子到水井的距离和最短。

设某一房子的两端点分别为(1,3),(3,3)。若水井的横坐标1〈=x〈=3, 则水井到房子的距离为 abs(水井纵坐标-1),即图中L1,否则(x〈 1 或 x 〉3),距离为min{水井到左端点的距离,水井到右端点的距离},即图中L2。换句话说,让村民们来打水所走的距离和最短。

输入格式

输入文件village.in的第一行为一个正整数N(N〈=100)。

接下来N行输入N座房子的信息,每行为四个非负整数,分别表示房子两端点的坐标。

房子的所有坐标都为0到100间的非负整数。

输出格式

输出文件village.out有且仅有一行,为所求的最短距离(保留两位小数)。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论