蓝桥杯-算法提高 两条直线

问题描述

给定平面上n个点。

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

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

输入格式

第一行包含一个数n。

接下来n行,每行包含两个整数,表示n个点的坐标(横纵坐标的绝对值小于109)。

输出格式

输出一个值,表示最小的最大曼哈顿距离的值,保留一位小数。

样例输入

4
1 0
0 1
2 1
1 2

样例输出

1.0

数据规模与约定

对于30%的数据,n<=100。

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

对于100%的数据,n<=105。

参考代码

此处为隐藏的内容!
发表评论并刷新,才能查看
俊霖

发表评论

您必须

目前评论:34   其中:访客  33   博主  1

  1. 李雪儿 5

    呵呵,好文一定要顶,支持

  2. yiyangqianxi 4

    学习

  3. 漠雨·陰晴雨 5

    点个赞

  4. 机智滴斌哥 5

    看看是不是我要的

  5. 5

    学习

  6. lh664693444 0

    讲得很好

  7. xiaweiyidengwo 4

    写的很好

  8. Maxwell 1

    学习学习

  9. 4

    学习,来看看代码

  10. Merc_A 1

    学习,来看看代码

  11. 14 K 0

    来看看

  12. 笃定 0

    666和腻害

  13. unrequited_love 1

    看看!!!!!!!!!!!!!!

  14. ymx200181 5

    看看

  15. abab99 2

    ..让我看看隐藏

  16. 倒e朵* 2

    来学习

  17. HE 0

    看一下真麻烦

  18. 独演、結侷 1

    学习一下

  19. 梁笨蛋的猫猫 0

    学习学习

  20. 0

    谢谢参考!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  21. ltc9206 0

    学习中

  22. zhuhui 2

    支持

  23. 知足 0

    学习

  24. 睡不醒的暮寒 0

    ………………….啊

  25. 【努力才幸福】 0

    学习

  26. afds 1

    的手法对付

  27. yeyue1992 1

    看看~

  28. 倚楼听风201201 0


    看题解

  29. LiGuangHua 1

    哈哈哈,想看

  30. 1172388661 0

    有Java代码吗

  31. LingAlReis 0

    好文一定要顶,支持

  32. yjz 0

    好评 谢谢

  33. zpand147840281 0

    真好