T5 雨水收集系统
metaphysis · · 题解
题目链接
本题是一道典型的计算几何题目。需要解题者掌握凸包和半平面交的求解方法。
题目给定的降雨云是一个凸多边形，当将其进行平移操作后，其路径所覆盖的区域也是一个凸多边形，这个凸多边形应该如何求呢？很简单，将平移后的各个凸包顶点求出来，与原来的凸包顶点一起，再求一次凸包即可。知道了降雨云覆盖的区域，将其与建筑顶面的矩形作半平面交，求出各个交的面积，然后累加即可。
主要注意实现的细节即可。
#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;
}