1 条题解

  • 0
    @ 2025-5-6 2:44:47

    解题思路:

    本题要求计算完全位于省份多边形内的区(单位正方形)的数量。每个区的边角点坐标为整数,需判断其是否完全被多边形包含。核心思路是通过扫描线算法遍历每个可能的区,判断其与多边形的包含关系。

    关键步骤:

    多边形边处理:将多边形的边转化为线段,并按最低点的yy坐标排序,便于扫描线处理。
    扫描线遍历:沿yy轴方向逐行扫描,对每个yy值处理所有相关的水平线段。
    交点计算:确定扫描线与多边形边的交点,按xx坐标排序,形成覆盖区间。
    区间覆盖统计:根据交点的奇偶性,判断区间的覆盖状态,累加完全覆盖的区数量。

    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
    上传者