Algoogle

Algorithm for Programming Contest

AOJ 1242 Area of Polygons

Category: AOJ Tag: geometry, line-sweep

Area of Polygons

問題概要


頂点が格子点上にある多角形が与えられる.
多角形が通るマスと多角形に含まれるマスの数を答えよ.

解法


y軸に平行な太さが1マス分の走査線で平面走査する.
各線分から現在見てる区間を切り取って,左側のx座標でソートする.
あとは足される区間と足さない区間が交互にくるので足してやればいい.
y軸に平行な線分は無視.

コード


(1242.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
int n, x[128], y[128];

double cpx(int p, int q, int i)
{
        if(y[p] < y[q]) swap(p,q);
        double a = y[p]-i, b = i-y[q];
        return (b*x[p]+a*x[q])/(a+b);
}

int solve()
{
        int ans = 0, li = *min_element(y,y+n), ri = *max_element(y,y+n);
        for (int i = li; i < ri; i++) {
                vector<pair<double,double>> xs;
                for (int j = 0; j < n; j++) {
                        int nj = (j+1)%n;
                        if(y[j] == y[nj] or i < min(y[j], y[nj]) or i+1 > max(y[j], y[nj])) continue;
                        double x1 = cpx(j,nj,i), x2 = cpx(j,nj,i+1);
                        if(x1 > x2) swap(x1, x2);
                        xs.push_back(make_pair(x1,x2));
                }
                sort(begin(xs),end(xs));
                int xr = -2048;
                for (int j = 0; j < (int)xs.size()-1; j+=2) {
                        int l = max(int(floor(xs[j].first)), xr), r = ceil(xs[j+1].second);
                        ans += r-l;
                        xr = r;
                }
        }
        return ans;
}

bool input()
{
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d %d", x+i, y+i);
        return n;
}

int main()
{
        while(input()) printf("%d\n", solve());
        return 0;
}

Comments