【2011集训队出题】信号塔

Description：

lanwuni接到一个任务，在C市建立N个信号塔来完成城市中的通讯任务。 　　假设C市是一个坐标范围[-2000000,2000000]的网格，一些整点上有用户，你也可以在整点上建立信号塔。一个点上可以建立多座。 在C市，两点之间的距离是曼哈顿距离，也就是横纵坐标差值之和。每个信号塔都有一个半径Di，表示与i曼哈顿距离不超过Di的地方都能被这个信号塔的信号覆盖到。 　　建立信号塔要满足一些性质： 　　1. 每个信号塔有一定的用户，lanwuni要把信号塔建立在某个地方，使得属于该塔的用户都能被信号覆盖到； 　　2. 信号塔有一定等级和安装限制，所以，第i号信号塔能覆盖的所有整点，必须也被第i+1号信号塔覆盖到。即使这个整点上没有用户。 　　现在告诉你每个信号塔的半径，以及每个信号塔的用户，请你帮lanwuni谋划一下应该把这N个信号塔建立在什么地方。 100%的数据中，1<=N,M<=100000，|Xi|,|Yi|,|Di|<=1000000。 题目附有Special Judge

题解：

首先对每个用户，合法的信号塔的位置是一个菱形。

那么这样一直合并，最后是一个平行四边形。

但是不好合并。

所以先把所有点旋转45°，避免小数运算，乘上 2√

变成了矩形合并问题，去min、max就行了。

求出最大的信号塔的范围后，随便选一个点，注意要抱证奇偶性相同，不然还回去就不存在。

选出来后，再倒退，去约束范围。

#include<cstdio>
#include<algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
using namespace std;

const int N = 1e5 + 5;

struct node {
    int u, x, y;
} a[N], as[N];

int n, m, x, y, d[N];

struct jx {
    int z, y, s, x;
} b[N], c[N], p;

bool cmp(node a, node b) {return a.u < b.u;}

void bin(jx &a, jx b) {
    a.z = max(a.z, b.z); a.x = max(a.x, b.x);
    a.y = min(a.y, b.y); a.s = min(a.s, b.s);
}

node G(jx a) {
    node b;
    b.x = a.z; b.y = a.x;
    if((b.y - b.x) % 2) {
        if(a.z != a.y) b.x ++; else b.y ++;
    }
    return b;
}

int main() {
    scanf("%d %d", &n, &m);
    fo(i, 1, n) scanf("%d", &d[i]);
    fo(i, 1, m) scanf("%d %d %d", &a[i].u, &a[i].x, &a[i].y);
    fo(i, 1, n) {
        b[i].z = b[i].x = -1e8;
        b[i].y = b[i].s = 1e8;
    }
    fo(i, 1, m) {
        x = a[i].x, y = a[i].y;
        a[i].x = x - y; a[i].y = x + y;
        int c = d[a[i].u];
        p.z = a[i].x - c; p.y = a[i].x + c;
        p.x = a[i].y - c; p.s = a[i].y + c; 
        bin(b[a[i].u], p);
    }
    c[n] = b[n];
    fd(i, n - 1, 1) {
        int r = d[i + 1] - d[i];
        c[i] = b[i];
        p.z = c[i + 1].z - r;
        p.y = c[i + 1].y + r;
        p.x = c[i + 1].x - r;
        p.s = c[i + 1].s + r;
        bin(c[i], p);
    }
    fo(i, 1, n)  {
        as[i] = G(c[i]);
        if(i == n) continue;
        int r = d[i + 1] - d[i];
        p.z = as[i].x - r;
        p.y = as[i].x + r;
        p.x = as[i].y - r;
        p.s = as[i].y + r;
        bin(c[i + 1], p);
    }
    fo(i, 1, n) printf("%d %d
", (as[i].x + as[i].y) / 2, (-as[i].x + as[i].y) / 2);
}