P5093: 村庄-【2021暑期训练】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间的非负整数。
【输出】
仅有一行，为所求的最短距离（保留两位小数）。
【输入输出样例】

village.in	village.out
3 0 0 0 1 2 2 3 2 4 4 4 3	4.47

【数据规模】
对于100%数据,N<=100

【提示】

村庄 解题报告

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

题目类型~

模拟赛-2021暑期训练 

咻咻~

提交答案 状态 返回