http://poj.org/problem?id=3148
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=255&page=show_problem&problem=1703

考察每条线段,对多边形进行梯形剖分。
按顺时针方向看,如果一条有向线段是向着 -x 轴的,那么它的下方形成的面积为负;如果一条有向线段是向着 +x 轴的,那么它的下方形成的面积为正。我们可以据此累加面积。
对每个梯形细条,分成三部分讨论,如下图:(只考察右边 1*5 的区域)

对于 ①,我们可从上往下算,每次减去前面的三角形面积就为当前梯形的面积。
对于 ②,用梯形面积减去 ① 中最后算出的三角形面积。
对于 ③,面积为 1 或 -1,这取决于这条线段的朝向。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 16ms, 244KB */

const int mx = 1e2 + 5;
const double eps = 1e-8;

struct pt {
    int x, y;
    pt() {}
    pt(int x, int y): x(x), y(y) {}
    void read() {SII(x, y);}
    pt operator - (const pt& a) {return pt(x - a.x, y - a.y);}
} p[mx], dir;

double A[mx][mx];

void print(double a) {
    if (a + eps < 0.25) PC('.');
    else if (a + eps < 0.5) PC('+');
    else if (a + eps < 0.75) PC('o');
    else if (a + eps < 1.0) PC('$');
    else PC('#');
}

int main() {
    int n, w, h, i, j, sign, ly1, ry1, LX, RX, x, up, down;
    double xdy, k, ly, ry, uy, prevS, nowS, dx;
    SIII(n, w, h);
    For(i, n) p[i].read();
    p[n] = p[0];
    For(i, n) {
        dir = p[i + 1] - p[i];
        if (dir.x == 0) continue;
        if (dir.x > 0) {
            LX = p[i].x, RX = p[i + 1].x;
            ly = p[i].y;
            sign = 1;
        } else {
            dir.x = -dir.x, dir.y = -dir.y;
            LX = p[i + 1].x, RX = p[i].x;
            ly = p[i + 1].y;
            sign = -1;
        }
        xdy = fabs((double)dir.x / dir.y);
        k = (double)dir.y / dir.x;
        ry = ly + k; // ly, ry 为当前细条梯形的两个角的纵坐标
        ly1 = int(ly + eps), ry1 = int(ry + eps);
        Forr(x, LX, RX) {
            // 计算当前这一竖条
            up = max(ly1, ry1), down = min(ly1, ry1); // [down+1, up] 为第 ① 部分的纵坐标范围
            prevS = 0.0;
            if (up > down) {
                uy = (up == ly1 ? ly : ry);
                dx = xdy * (uy - up);
                rForr(j, up, down + 1) {
                    nowS = dx * (uy - j) * 0.5;
                    A[j][x] += sign * (nowS - prevS);
                    prevS = nowS, dx += xdy;
                }
            }
            A[down][x] += sign * ((ly - down + ry - down) * 0.5 - prevS); // 第 ② 部分
            For(j, down) A[j][x] += sign; // 第 ③ 部分
            ly = ry, ry += k;
            ly1 = ry1, ry1 = int(ry + eps);
        }
    }
    rFor(i, h - 1) {
        For(j, w) print(A[i][j]);
        Pn();
    }
    return 0;
}

Comments

comments powered by Disqus