问题 5451. -- 村庄-【2014暑期训练】T1Day1T1

5451: 村庄-【2014暑期训练】T1Day1T1

时间限制: 1 Sec  内存限制: 256 MB
献花: 42  解决: 13
[献花][花圈]

题目描述

2. 村庄

【问题描述】

村庄的结构很简单。我们设整个村庄处在一个坐标系的第一象限。村庄里有N座房子,为方便计算,对村庄中的房子作理想化的假设:

(1)它很扁,可以近似得看做一条直线;

(2)它还是平行于坐标轴的;

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

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



【输入】

第一行为一个正整数N(N〈=100)。

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

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

【输出】

仅有一行,为所求的最短距离(保留两位小数)。

【输入输出样例】

village.in

village.out

3

0 0 0 1

2 2 3 2

4 4 4 3

4.47

【数据规模】

对于100%数据,N<=100

输入

输出

提示


村庄 解题报告



题意很简单。直观地想到搜索。由于坐标范围为【0100】,搜整点的话复杂度是完全允许的。但显然,只搜整点是不够的,事实证明只搜整点与正确结果相差很大,那么,要考虑实点。注意到输出只要求保留两位,我们再搜过整点之后,答案所需的实点就在最优的整点附近。,所以我们可以先枚举依次整点,取前K优的整点(事实证明:取K=6,可以AC),再搜索这些点附近的实点(小数点后两位),就可以得到一个近似最优解(显然这不是完全最优,但对于保留小数足够了。)

来源

[献花][花圈]