1 条题解
-
0
解题思路:
本题要求计算完全位于省份多边形内的区(单位正方形)的数量。每个区的边角点坐标为整数,需判断其是否完全被多边形包含。核心思路是通过扫描线算法遍历每个可能的区,判断其与多边形的包含关系。
关键步骤:
多边形边处理:将多边形的边转化为线段,并按最低点的坐标排序,便于扫描线处理。
扫描线遍历:沿轴方向逐行扫描,对每个值处理所有相关的水平线段。
交点计算:确定扫描线与多边形边的交点,按坐标排序,形成覆盖区间。
区间覆盖统计:根据交点的奇偶性,判断区间的覆盖状态,累加完全覆盖的区数量。C++实现:
#include <cstdio> #include <algorithm> #include <complex> #include <cmath> using namespace std; typedef complex<int> PL; // 整数坐标点(x为实部,y为虚部) typedef complex<double> P; // 双精度坐标点,用于交点计算 inline long long cross(const PL& a, const PL& b) { return (long long)a.real()*b.imag() - (long long)b.real()*a.imag(); } struct line { PL a, b; line(PL p, PL q) : a(p), b(q) {} }; struct segment { PL a, b; segment(PL x, PL y) : a(x), b(y) {} // 判断线段与直线的相交类型 int intersects(const line& ln) const { long long x = cross(ln.b - ln.a, a - ln.a); long long y = cross(ln.b - ln.a, b - ln.a); if (x == 0 && y == 0) return 0; // 重合 if (x == 0 || y == 0) return 1; // 端点在线段上 if ((x > 0) ^ (y > 0)) return 3; // 相交 return 4; // 不相交 } // 计算交点(假设已相交) P intersection(const line& ln) const { PL x_dir = b - a; PL y_dir = ln.b - ln.a; double t = (double)cross(y_dir, ln.a - a) / cross(y_dir, x_dir); return P(a.real(), a.imag()) + P(x_dir.real(), x_dir.imag()) * t; } }; struct by_y { bool operator()(const segment& l, const segment& r) const { int min_l = min(l.a.imag(), l.b.imag()); int min_r = min(r.a.imag(), r.b.imag()); return (min_l != min_r) ? (min_l < min_r) : (max(l.a.imag(), l.b.imag()) < max(r.a.imag(), r.b.imag())); } }; int main() { vector<PL> points; int x, y; while (scanf("%d %d", &x, &y) == 2) { points.push_back(PL(x, y)); } int n = points.size(); vector<segment> edges; for (int i = 0; i < n; ++i) { edges.push_back(segment(points[i], points[(i+1)%n])); } sort(edges.begin(), edges.end(), by_y()); long long total = 0; for (int y_scan = 0; y_scan < 100000; ++y_scan) { vector<double> intersections; line scan_line(PL(0, y_scan), PL(1, y_scan)); for (const auto& edge : edges) { int res = edge.intersects(scan_line); if (res == 3 || res == 1) { P p = edge.intersection(scan_line); intersections.push_back(p.real()); } } sort(intersections.begin(), intersections.end()); for (size_t i = 0; i < intersections.size(); i += 2) { int start = ceil(intersections[i]); int end = floor(intersections[i+1]); if (start <= end) { total += end - start + 1; } } } printf("%lld\n", total); return 0; }
- 1
信息
- ID
- 1575
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 1
- 上传者