自动搬运

查看原文

来自洛谷，原作者为

	metaphysis 故不积跬步，无以至千里；不积小流，无以成江海。——《荀子·劝学篇》

搬运于2025-08-24 22:29:28，当前版本为作者最后更新于2020-11-05 08:32:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

本题是一道典型的计算几何题目。需要解题者掌握凸包和半平面交的求解方法。

题目给定的降雨云是一个凸多边形，当将其进行平移操作后，其路径所覆盖的区域也是一个凸多边形，这个凸多边形应该如何求呢？很简单，将平移后的各个凸包顶点求出来，与原来的凸包顶点一起，再求一次凸包即可。知道了降雨云覆盖的区域，将其与建筑顶面的矩形作半平面交，求出各个交的面积，然后累加即可。

主要注意实现的细节即可。

#include <bits/stdc++.h>

using namespace std;

const int MAXV = 1100;
const double EPSILON = 1E-7;

// 表示点的数据结构
struct point {
    double x, y;
    point (double x = 0, double y = 0): x(x), y(y) {}
    point operator + (point p) { return point(x + p.x, y + p.y); };
    point operator - (point p) { return point(x - p.x, y - p.y); };
    point operator * (double k) { return point(x * k, y * k); };
    point operator / (double k) { return point(x / k, y / k); };
    
    bool operator<(const point &p) const
	{
	    if (fabs(y - p.y) > EPSILON) return y < p.y;
	    return x < p.x;
	}
	
	bool operator==(const point &p) const
	{
	    return fabs(x - p.x) <= EPSILON && fabs(y - p.y) <= EPSILON;
	}
};

// 定义多边形
typedef vector<point> polygon;


// 范数
double norm(point a)
{
    return a.x * a.x + a.y * a.y;
}

// 模
double abs(point a)
{
    return sqrt(norm(a));
}

// 内积（点积）
double dot(point a, point b)
{
    return a.x * b.x + a.y * b.y;
}

// 外积（叉积）
double cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}

// 定义直线，使用两点和极角定义直线，加入极角是用于半平面交
struct line
{
    point a, b;
    double angle;
};

// 有向面积
double cp(point a, point b, point c)
{
    return cross(b - a, c - a);
}

// 利用有向面积判断顺时针旋转
bool cw(point a, point b, point c)
{
    return cp(a, b, c) < -EPSILON;
}

// 利用有向面积判断逆时针旋转
bool ccw(point &a, point &b, point &c)
{
    return cp(a, b, c) > EPSILON;
}

// 利用有向面积判断逆时针旋转或共线
bool ccwOrCollinear(point &a, point &b, point &c)
{
    double cp1 = cp(a, b, c);
	return cp1 > EPSILON || fabs(cp1) <= EPSILON;
}

// 利用 Andrew 合并法求凸包
polygon andrewConvexHull(polygon pg)
{
	polygon ch;

    sort(pg.begin(), pg.end());
	for (int i = 0; i < pg.size(); i++)
	{
		while (ch.size() >= 2 &&
		    ccwOrCollinear(ch[ch.size() - 2], ch[ch.size() - 1], pg[i]))
			ch.pop_back();
		ch.push_back(pg[i]);
	}
	for (int i = pg.size() - 1, upper = ch.size() + 1; i >= 0; i--)
	{
		while (ch.size() >= upper &&
		    ccwOrCollinear(ch[ch.size() - 2], ch[ch.size() - 1], pg[i]))
			ch.pop_back();
		ch.push_back(pg[i]);
	}
    ch.pop_back();
    
	return ch;
}

// 按极角对直线进行排序的比较函数
bool cmpLine(line p, line q)
{
    if (fabs(p.angle - q.angle) <= EPSILON) return cw(p.a, p.b, q.a);
    return p.angle < q.angle;
}

// 按极角对直线进行去重的比较函数
bool cmpAngle(line p, line q)
{
    return fabs(p.angle - q.angle) <= EPSILON;
}

// 判定两条直线是否平行
bool parallel(line p, line q)
{
    return fabs((p.a.x - p.b.x) * (q.a.y - q.b.y) -
        (q.a.x - q.b.x) * (p.a.y - p.b.y)) <= EPSILON;
}

// 确定两条直线的交点
point getIntersection(line p, line q)
{
    point p1 = p.a;
    double scale =
        ((p.a.x - q.a.x) * (q.a.y - q.b.y) - (p.a.y - q.a.y) * (q.a.x - q.b.x)) /
        ((p.a.x - p.b.x) * (q.a.y - q.b.y) - (p.a.y - p.b.y) * (q.a.x - q.b.x));
    p1.x += (p.b.x - p.a.x) * scale;
    p1.y += (p.b.y - p.a.y) * scale;
    return p1;
}

// 根据两点确定一条直线
line pointToLine(point a, point b)
{
    line lr;
    lr.a = a, lr.b = b, lr.angle = atan2(b.y - a.y, b.x - a.x);
    return lr;
}

// 使用朱泽园介绍的“排序增量法”求半平面交
polygon halfPlaneIntersection(line *sides, int nLine)
{
    polygon pg;
    line deq[MAXV];

    sort(sides, sides + nLine, cmpLine);
    nLine = unique(sides, sides + nLine, cmpAngle) - sides; 

    int btm = 0, top = 1;
    deq[0] = sides[0], deq[1] = sides[1];

    for (int i = 2; i < nLine; i++)
    {
        if (parallel(deq[top], deq[top - 1]) || parallel(deq[btm], deq[btm + 1]))
            return pg;

        while (btm < top &&
            cw(sides[i].a, sides[i].b, getIntersection(deq[top], deq[top - 1])))
            top--;
        while (btm < top &&
            cw(sides[i].a, sides[i].b, getIntersection(deq[btm], deq[btm + 1])))
            btm++;

        deq[++top] = sides[i];
    }

    while (btm < top &&
        cw(deq[btm].a, deq[btm].b, getIntersection(deq[top], deq[top - 1])))
        top--;
    while (btm < top &&
        cw(deq[top].a, deq[top].b, getIntersection(deq[btm], deq[btm + 1])))
        btm++;

    if (top <= (btm + 1)) return pg;

    for (int i = btm; i < top; i++)
        pg.push_back(getIntersection(deq[i], deq[i + 1]));
    if (btm < (top + 1))
        pg.push_back(getIntersection(deq[btm], deq[top]));

    return pg;
}

// 计算多边形的面积
double getArea(polygon pg)
{
    if (pg.size() < 3) return 0.0;
    double A = 0.0;
    int n = pg.size();
    for (int i = 0, j = (i + 1) % n; i < n; i++, j = (i + 1) % n)
        A += (pg[i].x * pg[j].y - pg[j].x * pg[i].y);
    return fabs(A / 2.0);
}

// 根据对角顶点坐标确定矩形
polygon getRectFromPoint(int x1, int y1, int x2, int y2)
{
    polygon rect;
    int minx = min(x1, x2), maxx = max(x1, x2);
    int miny = min(y1, y2), maxy = max(y1, y2);
    rect.push_back(point(minx, miny));
    rect.push_back(point(maxx, miny));
    rect.push_back(point(maxx, maxy));
    rect.push_back(point(minx, maxy));
    return rect;
}

// 解析时间
int getTime(string text)
{
    return stoi(text.substr(0, 2)) * 60 + stoi(text.substr(3));
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    int cases, n, m, v;
    string time1, time2;

    cin >> cases;
    for (int cs = 1; cs <= cases; cs++)
    {
        cin >> n;
        
        // 读入每栋建筑的对角点坐标，由对角点坐标确定矩形，矩形的顶点按逆时针排列。
        vector<polygon> rects;
        int x1, y1, x2, y2;
        for (int i = 0; i < n; i++)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            rects.push_back(getRectFromPoint(x1, y1, x2, y2));
        }
        
        // 读入降雨云。
        polygon cloud;
        cin >> m;
        for (int i = 0; i < m; i++)
        {
            cin >> x1 >> y1;
            cloud.push_back(point(x1, y1));
        }
        
        // 降雨云沿着直线方向做平移运动，其扫过的区域构成一个凸多边形。使用凸包算法求出凸多边形的顶点，顶点按照逆时针方向排序。
        point s, e;
        cin >> s.x >> s.y >> e.x >> e.y;
        cin >> v >> time1 >> time2;
        double d = v * (getTime(time2) - getTime(time1));
        int cnt = cloud.size();
        for (int i = 0; i < cnt; i++)
        {
            point moved = cloud[i] + (e - s) * d / abs(e - s);
            cloud.push_back(moved);
        }
        cloud = andrewConvexHull(cloud);
        reverse(cloud.begin(), cloud.end());

        // 使用半平面交确定降雨云与每栋建筑的顶层的交，计算面积并求和。
        double area = 0;
        line sides[MAXV];
        for (int i = 0; i < rects.size(); i++)
        {
            int nLine = 0;
            for (int j = 0; j < cloud.size(); j++)
                sides[nLine++] = pointToLine(cloud[j], cloud[(j + 1) % cloud.size()]);
            for (int j = 0; j < rects[i].size(); j++)
                sides[nLine++] = pointToLine(rects[i][j], rects[i][(j + 1) % rects[i].size()]);
            area += getArea(halfPlaneIntersection(sides, nLine));
        }
        cout << fixed << setprecision(1) << area << '\n';
    }

    return 0;
}