如何用二分法和枚举法高效求解两条直线交点问题？

本文共计1222个文字，预计阅读时间需要5分钟。

题目：算法提升——两条直线资源限制问题描述：给定平面上的n个点，要求在1.0s内，内存限制256.0MB内，找出两条互相垂直的直线。

试题算法提高两条直线资源限制时间限制1.0s内存限制256.0MB问题描述给定平面上n个点。求两条直线这两条直线互相垂直1.0s 内存限制256.0MB 问题描述 给定平面上n个点。

求两条直线这两条直线互相垂直而且它们与x轴的夹角为45度并且n个点中离这两条直线的曼哈顿距离的最大值最小。

两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。

输入格式 第一行包含一个数n。

接下来n行每行包含两个整数表示n个点的坐标横纵坐标的绝对值小于10^9。

输出格式 输出一个值表示最小的最大曼哈顿距离的值保留一位小数。 样例输入 4 1 0 0 1 2 1 1 2 样例输出 1.0 数据规模与约定 对于30%的数据n<100。

对于另外30%的数据坐标范的绝对值小于100。

对于100%的数据n<105。

解题思路

这题挺难理解的刚上手不大有思路编者也是借鉴了blog.dotcpp.com/a/3702 首先明确题意点到直线的距离为点到两条直线距离中的较小者然后我们要找 所有点到直线的距离的最大值并且要这个最大值越小越好。