🌸 Gym 102770H - Huge Clouds

Gym 102770H - Huge Clouds - 计算几何 + 区间统计

Gym - 102770H

描述

在二维平面上给定$n$个点(星星)和$m$个线段(云)(均在$x$轴严格上方)。定义在$x$轴上一个点$u$在阴影中,当且仅当$u$和每个给定点$v$的连线都和某条给定线段相交(包括端点)。问$x$轴上阴影的长度(若长度$>10^9$则输出$-1$)。$n,m\le 500$。

做法

大致解法非常显然:做出每个星星对每个云在地面上的投影区间,离散化后用类似借教室的方法做区间合并即可。

对于每个 (星星, 云) 二元组,我们需要对其相对位置关系做分类讨论。设星星坐标为$(x_s, y_s)$,云左右端点的坐标为$(x_{c1}, y_{c1})$, $(x_{c2}, y_{c2})$:

  1. 云(含端点)恰好经过星星。那么这颗星星是完全不可见的,可以将其事先排除。

  2. 云的两个端点都不在星星的严格下方,即$y_{c1}, y_{c2}\le y_s$。这时不会形成任何阴影。

  3. 云的两个端点都在星星的严格下方$y_{c1}, y_{c2}\le y_s$。这时会形成有限长度的阴影,且阴影左端点就是射线$(x_s, y_s)-(x_{c1}, y_{c1})$与$x$轴交点,阴影右端点亦然。

  4. 云的一个端点在星星的严格下方,另一个端点不在星星的严格下方。这时会形成一条射线状的无限长阴影。星星与云的较低端点连线与$x$轴交点就是阴影射线的端点;至于这条射线是朝哪里射的,只需判断水平直线$y=y_s$与云线段交点在星星的左边还是右边即可。这是一种较为简洁的处理方式。我训练赛时没有考虑清楚,判断得太复杂且有错误。

到这里似乎差不多了,但还有一个细节:平行于$y$轴的竖直云。如果一个星星的横坐标与某竖直云的横坐标相同,那么其阴影至多为一个点,因此直接忽略之即可。

其实还有问题:竖直云的端点是没有左右之分的!因此,对于上面所列的情况3,我们不应该通过区分云的左右端点来区分阴影的左右端点,而应该先把两个投影点算出来,再去判断谁在左谁在右。WA在这个细节上的教训在于,能直接用计算结果时就少用推论。

至此,计算几何得部分就考虑得比较完整了。接下来需要做区间合并和统计。对点离散化之后,我们需要统计每段被多少个不同的点覆盖了。因为一个星星的阴影区间可能会发生重叠,所以我们必须分别维护$n$个点的覆盖次数。

首先明确一下数据规模。$n,m\le 500$,最多有$500\times 500 \times 2 = 5 \times 10^5$个交点。因此,暴力方法(对每个交点维护一个$n$维向量,存储这个点上的差分值)在时间和空间上都是不可行的。所以,可以用一个map存储每个点上的差分值映射。最后累加前缀和统计时,只考察有变化的那些维度。因为这个map的大小是星星数$n\le 500$,所以是可以接受的。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define dep(i, a, b) for (int i = a; i >= b; i--)
#define vep(i, v) for (int i = 0; i < (int)v.size(); i++)
#define fill(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define mp make_pair

const double eps = 1e-9, INF = 1e15;
inline double sqr(double x) { return x*x; }
const int N = 500 + 5;

int cmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double a, double b): x(a), y(b) {}
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    friend Point operator + (const Point &a, const Point &b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point operator - (const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend bool operator == (const Point &a, const Point &b) {
        return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0;
    }
    friend Point operator * (const Point &a, const double &b) {
        return Point(a.x*b, a.y*b);
    }
    friend Point operator * (const double &a, const Point &b) {
        return Point(a*b.x, a*b.y);
    }
    friend Point operator / (const Point &a, const double &b) {
        return Point(a.x/b, a.y/b);
    }
    double norm() {
        return sqrt(sqr(x) + sqr(y));
    }
};

double dot(const Point &a, const Point &b) {
    return a.x*b.x + a.y*b.y;
}
double det(const Point &a, const Point &b) {
    return a.x*b.y - a.y*b.x;
}
double dist(const Point &a, const Point &b) {
    return (a - b).norm();
}

struct Line {
    Point a, b;
    Line() { }
    Line(Point x, Point y): a(x), b(y) {}
    void input() {
        a.input(), b.input();
    }
};

Line point_make_line(const Point a, const Point b) {
    return Line(a, b);
}
bool point_on_segment(const Point p, const Line l) {
    Point s = l.a, t = l.b;
    return cmp(det(p - s, t - s)) == 0 && cmp(dot(p - s, p - t)) <= 0;
}
bool parallel(Line x, Line y) {
    return !cmp(det(x.a - x.b, y.a - y.b));
}
bool line_make_point(Line x, Line y, Point &res) {
    if (parallel(x, y)) return false;
    double s1 = det(x.a - y.a, y.b - y.a);
    double s2 = det(x.b - y.a, y.b - y.a);
    res = (s1*x.b - s2*x.a) / (s1 - s2);
    return true;
}

typedef pair<double, int> pdi;

int T, n, m;
Point star[N];
pdi inter[2 * N * N];
double xp[2 * N * N];
map<int, int> mark[2 * N * N];
int now[N];
Line cloud[N];
bool visible[N];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("h.in", "r", stdin);
    #endif

    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        rep(i, 1, n) star[i].input();
        rep(i, 1, m) {
            cloud[i].a.input();
            cloud[i].b.input();
        }
        Line hor = Line(Point(0.0, 0.0), Point(1.0, 0.0));
        rep(i, 1, n) visible[i] = true;
        rep(i, 1, n) rep(j, 1, m) {
            if (!visible[i] || point_on_segment(star[i], cloud[j])) {
                visible[i] = false;
                break;
            }
        }
        int total_visible = 0;
        rep(i, 1, n) total_visible += visible[i];
        if (total_visible == 0) {
            puts("-1");
            continue;
        }

        int cnt = 0;
        rep(i, 1, n) {
            if (!visible[i]) continue; 
            rep(j, 1, m) {
                Point res1, res2, a = cloud[j].a, b = cloud[j].b;

                if (cmp(a.y - star[i].y) >= 0 && cmp(b.y - star[i].y) >= 0) continue;
                if (cmp(a.x - star[i].x) == 0 && cmp(b.x - star[i].x) == 0) continue;

                if (cmp(a.y - star[i].y) < 0 && cmp(b.y - star[i].y) < 0) {
                    line_make_point(Line(star[i], a), hor, res1);
                    line_make_point(Line(star[i], b), hor, res2);
                    if (res1.x > res2.x) swap(res1, res2);
                    inter[++cnt] = mp(res1.x, i);
                    inter[++cnt] = mp(res2.x, -i);
                    continue;
                }

                Point p;
                line_make_point(
                    point_make_line(star[i], Point(star[i].x + 1, star[i].y)), 
                    cloud[j], 
                    p);
                Point lower = cmp(a.y - b.y) < 0 ? a : b;
                line_make_point(Line(star[i], lower), hor, res1);
                if (p.x > star[i].x) {
                    inter[++cnt] = mp(res1.x, i);
                    inter[++cnt] = mp(INF, -i);
                }
                else {
                    inter[++cnt] = mp(-INF, i);
                    inter[++cnt] = mp(res1.x, -i);
                }
            }
        }
        sort(inter + 1, inter + cnt + 1);
        rep(i, 1, cnt) xp[i] = 0;
        rep(i, 1, cnt) mark[i].clear();
        int t = 0, i = 1;
        while (i <= cnt) {
            t++;
            xp[t] = inter[i].first;
            int tmp = inter[i].second;
            if (tmp > 0) mark[t][tmp]++;
            else mark[t][-tmp]--;
            while (i < cnt && cmp(xp[t] - inter[i + 1].first) == 0) {
                i++;
                int tmp = inter[i].second;
                if (tmp > 0) mark[t][tmp]++;
                else mark[t][-tmp]--;
            } 
            i++;
        }
        double ans = 0, pre;
        bool flag = false;
        int sum = 0;
        fill(now, 0);
        rep(i, 1, t) {
            for (auto mk: mark[i]) {
                int pre = now[mk.first];
                now[mk.first] += mk.second;
                if (pre == 0 && now[mk.first] > 0) sum++;
                else if (pre > 0 && now[mk.first] == 0) sum--;
            }
            if (!flag && sum == total_visible) {
                pre = xp[i];
                flag = true;
            }
            else if (sum < total_visible && flag) {
                ans += (xp[i] - pre);
                flag = false;
            }
            if (ans > 1e9) break;
        }
        if (ans > 1e9) puts("-1");
        else printf("%.10lf\n", ans);
    }
    return 0;
}

Powered by Jekyll and Theme by solid
皖ICP备2021005418号-1