ACM2011大连区域赛网络预选赛 H-1008 Parent and son

2011-09-03T20:10:00.000+08:00

今天去大连区域赛的网络预选赛打了一次酱油，结果被虐翻了……才6题，罚时也巨高，原本应该能够更好的……

H题，一棵N个结点的树，结点从1~N编号。然后有M次询问，每次询问是两个数i, j，表示以i为根结点，求j的所有儿子中编号最小的结点（F值）以及j的所有子孙中编号最小的结点（G值），如果j是叶子结点则输出"no answers!"。

这个题其实也不是很难，但是很麻烦很恶心，首先我们先任意建树（即任选一个结点为根），我们称之为原树。可以发现若i不是j的子孙，那么j的子孙就是原树中的子孙；然而，若i是j的子孙，则有些麻烦：设从j走到i必须经过j的某个儿子k，首先在原树中不是j的子孙的结点在新树中都变成了j的子孙（不包括j本身），其次j的子孙还包括j在原树中除了k以外的其它儿子及其子孙结点。

现在问题已经很明朗了，首先我们对于每个结点，维护4个域：up_i, down_i, left_i, right_i，其中up表示（在原树中）不是i的子孙结点，down表示i的子孙结点，left, right分别表示i的左边和右边的所有兄弟结点，每个域都记录了F值和G值。我们需要做两遍深搜来求出所有的域值：第一遍求出down_i, left_i和right_i，然后第二遍可用left_i, right_i和up_i'求出up_i，其中i'为i的父亲结点。那么对于第一种情况，答案就是down_i；对于第二种，首先求出k，然后答案即可从left_k, right_k和up_i中取最小值得到。

在深搜的过程中，我们对于每个结点，在其入栈和出栈时分别打上一个时间戳，那么每个结点可以用一个区间来表示，j是i的祖先当且仅当j的区间包含了i的区间。那么怎么求出k点呢？对此我的做法是这样的：首先在深搜时求出每个结点的深度dep_i，那么显然k点就是i点往上走dep_i - dep_j - 1步。我们建立一个树形ST表，用F_i,j表示结点i往上走2^j步所到达的结点是哪个，然后显然我们可以在对数级别的时间内实现结点i往上走任意步了。不过这种实现把我的整个算法拉到了(N + M)logN的级别，不知道有没有更好的方法。

至此本题已经得到解决。

代码：（过几天放出）

最近圆对

2010-12-01T14:24:00.005+08:00

最近圆对是一个非常经典的计算几何问题，其大意为：给出N个两两不相交的圆，求相距最近的两个圆的距离。

我们先二分答案，将问题转换为判定性问题：判断能否找到距离≤a的一对圆。如果将每个圆的半径都增加a/2，那么实际上该问题就是判断是否有两圆相交（或者相切）。判断圆相交可以采用扫描线+平衡树的方法来实现。

对于每个圆(x, y, r)，有两个关键点：左边界和右边界，即x-r和x+r。首先我们对所有关键点进行排序，然后维护一颗以圆的y坐标为关键字的平衡树，对于每个关键点，如果它是左界，则将相对应的圆插入至平衡树，若为右界则做删除操作。我们只需在每次插入和删除操作时（设操作结点为i），判断i、i的前趋、i的后继这三个圆是否两两不相交。若出现相交，则说明答案≤a（能找到距离≤a的一对圆），否则答案>a。

该算法的时间复杂度为O(NlogNlogR)，其中R为答案的范围。

顺便提一句：如果圆的半径全部相等，则该题有复杂度更低的O(NlogN)的做法：最近点对。

代码：

#include <algorithm>
#include <set>
#include <stdio.h>
using namespace std;

const double ZERO = 1e-8;

struct Circle {
    double x, y, r;
};

struct Point {
    double x;
    bool in;
    long i;
};

Circle a[50000];
Point b[100000];
set<Circle> f;
set<Circle>::iterator s1, s2, s3;
long n, m;

Circle tmp;
long i;
double l = 0, r = 1e6, mid;

inline bool is_zero(const double x) {
    return -ZERO <= x && x <= ZERO;
}

inline bool cmp_point(const Point &a, const Point &b) {
    return a.x < b.x;
}

inline bool operator <(const Circle &a, const Circle &b) {
    return is_zero(a.y - b.y) ? a.x < b.x : a.y < b.y;
}

inline double sqr(const double x) {
    return x * x;
}

inline bool collide(const Circle &a, const Circle &b) {
    return sqr(a.x - b.x) + sqr(a.y - b.y) < sqr(a.r + mid + b.r + mid);
}

int main() {
    scanf("%ld", &n);
    for (i = 0; i < n; ++i) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);

    /*int j;double min=1e10,tp;
    for (i=0;i<n;++i)
        for (j=i+1;j<n; ++j) {
            tp=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y))-a[i].r-a[j].r;
            if (min>tp)min=tp;
        }
    printf("%.6lf\n",min);
    */
    while (r - l > ZERO) {
        mid = (l + r) * .5;
        for (m = 0, i = 0; i < n; ++i) {
            b[m].x = a[i].x - a[i].r - mid;
            b[m].in = true, b[m++].i = i;
            b[m].x = a[i].x + a[i].r + mid;
            b[m].in = false, b[m++].i = i;
        }
        sort(b, b + m, cmp_point);

        f.clear();
        tmp.x = tmp.y = -1e30, tmp.r = 0, f.insert(tmp);
        tmp.x = tmp.y = 1e30, f.insert(tmp);
        for (i = 0; i < m; ++i)
            if (b[i].in) {
                s1 = s2 = s3 = f.insert(a[b[i].i]).first;
                --s1, ++s3;
                if (collide(*s1, *s2) || collide(*s2, *s3) || collide(*s3, *s1)) break;
            } else {
                s1 = s2 = s3 = f.find(a[b[i].i]);
                --s1, ++s3;
                if (collide(*s1, *s2) || collide(*s2, *s3) || collide(*s3, *s1)) break;
                f.erase(s2);
            }
        i < m ? r = mid : l = mid;
    }

    printf("%.6lf", l * 2);
    return 0;
}

E478: Don't panic!

ACM2011大连区域赛网络预选赛 H-1008 Parent and son

最近圆对