bzoj1696专题

BZOJ1696: [Usaco2007 Feb]Building A New Barn新牛舍

n<=10000个点(xi,yi),找到一个不同于给出的所有点的点,使得该点到所有点的曼哈顿距离最小并找出这样的点的个数。 第一眼看上去这不是中位数嘛,奇数一个点偶数一片,然后找一下这篇区域有几个不符合的点即可。不过要找出“不同于给出的点”的点,那万一中位数那个点被占了,就找它四周四个点即可。 错误!明知道会有中位数那一个点被占了,那怎么就不考虑四周都被占了的情况? 不过可以肯定的是,离中位数越