解題區/解題區 - UVa

UVa 1641 - ASCII Area

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個用 ASCII Area 拉出來的簡單多邊形，求其面積為何？

Sample Input

1
2
3
4
5
4 4
/\/\
\../
.\.\
..\/

Sample Output

1
8

Solution

看別人的代碼相當簡單，只是有點不知道它們怎麼構思的。

首先，保證每一個端點都是格子點，靈機一動想到 Pick’s theorem,$A = i + b/2 - 1$，那麼接著就是找到 i 的個數 (內部存在的整數節點個數)，b 個數 (邊上的整數節點個數)。

b 很好求得，相當於 \ 和 / 的個數而已，然而 i 求法會比較特別一點，思路類似於掃描線的方式，性質則是利用射線法 (一個點拉一個射線無限延伸，如果該點在簡單多邊形內，則會穿過奇數個點。)。

如果是凸多邊形，也許就能用行列式求值。

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
#include <stdio.h> 
// Pick's theorem, A = i + b/2 - 1
int main() {
    char g[128][128];
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int B = 0, I = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '/' || g[i][j] == '\\')
                    B++;
            }
        }
        
        for (int i = 0; i <= n; i++) {
            int in = 0;
            for (int j = 0; j <= m; j++) {
                int f = 0;
                if (i-1 >= 0 && g[i-1][j] == '/' && g[i][j] == '\\')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j-1] == '/')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j] == '\\')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j] == '/' && g[i][j-1] == '/')
                    in++;
                if (i-1 >=0 && j-1 >= 0 && g[i-1][j-1] == '\\')	f = 1;
                if (i-1 >=0 && g[i-1][j] == '/')				f = 1;
                if (g[i][j] == '\\')							f = 1;
                if (j-1 >= 0 && g[i][j-1] == '/')				f = 1;
                if (!f && in%2 == 1)
                    I ++;
            }
        }
        printf("%d\n", I + B/2 - 1);
    }
    return 0;
}