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

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间的非负整数。

【输出】

仅有一行，为所求的最短距离（保留两位小数）。

【输入输出样例】

【数据规模】

对于100%数据,N<=100

村庄 解题报告

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