🔗 UVA-10242 Fourth Point !!

tags: 數學(Math), 幾何與座標, 計數(Counter)

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

UVA 上的測資最後有空白行，請注意。

題意

  • 給定平行四邊形中兩條 相鄰 邊的端點座標，求不屬於這兩條邊的最後一個點的座標。

LuckyCat 的中文翻譯

思路：數學(Math) + 幾何與座標 + 計數(Counter)

  • 這題利用了「平行四邊形中對角座標相加會相等」的性質，即 D=B+C−AD = B + C - A ，可以利用 向量 來證明。
  • 為方便說明，令重複點為 AA，即給定的兩條邊為 AB→\overrightarrow{AB} 和 AC→\overrightarrow{AC}，最後一個點為 DD；令 OO 為原點，則 AA 的座標即為 OA→\overrightarrow{OA}
    • 欲證 OA→+OD→=OB→+OC→\overrightarrow{OA} + \overrightarrow{OD} = \overrightarrow{OB} + \overrightarrow{OC}，即 OD→=OB→+OC→−OA→\overrightarrow{OD} = \overrightarrow{OB} + \overrightarrow{OC} - \overrightarrow{OA}
    • 由於是平行四邊形，所以 AD→=AB→+AC→\overrightarrow{AD} = \overrightarrow{AB} + \overrightarrow{AC}
    • 而 OB→=OA→+AB→\overrightarrow{OB} = \overrightarrow{OA} + \overrightarrow{AB} 、 OC→=OA→+AC→\overrightarrow{OC} = \overrightarrow{OA} + \overrightarrow{AC} ，代入 OB→+OC→−OA→\overrightarrow{OB} + \overrightarrow{OC} - \overrightarrow{OA} 中，得 (OA→+AB→)+(OA→+AC→)−OA→=OA→+AB→+AC→=OA→+AD→=AD→(\overrightarrow{OA} + \overrightarrow{AB}) + (\overrightarrow{OA} + \overrightarrow{AC}) - \overrightarrow{OA} = \overrightarrow{OA} + \overrightarrow{AB} + \overrightarrow{AC} = \overrightarrow{OA} + \overrightarrow{AD} = \overrightarrow{AD} ，得證。
  • 這題可以利用 Counter 來計算每個點的出現次數，出現兩次的點即為重複點，也就是上述的 AA 點。在計算時遇到重複點時，減去該點的座標；反之則加上該點的座標，即可得到最後一個點的座標。
  • 但由於出現次數只有兩次，也可以直接檢查四個點中重複的點是哪兩個，總共有 C24=6C^4_2 = 6 種組合，但顯然同一條邊上的兩點不會重複，所以只需要檢查 44 種組合即可。
  • 時間複雜度：O(1)O(1)，對於每次詢問。
  • 空間複雜度：O(1)O(1)，只需要常數空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import *

while (True):
    try:
        P = list(map(float, input().split()))
        if len(P) != 8: # UVA 上的測資最後有空白行
            break
    except:
        break

    cnt = Counter()
    for i in range(4):
        x, y = P[i * 2], P[i * 2 + 1]
        cnt[(x, y)] += 1
    x, y = 0, 0
    for (dx, dy), v in cnt.items():
        x += dx if v == 1 else -dx
        y += dy if v == 1 else -dy
    print(f"{x:.3f} {y:.3f}")
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
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    double x1, y1, x2, y2, x3, y3, x4, y4;
    while (cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4) {
        double x = 0, y = 0;
        if (x1 == x3 && y1 == y3) { // 重複點是p1, p3
            x = x2 + x4 - x1;
            y = y2 + y4 - y1;
        } else if (x1 == x4 && y1 == y4) { // 重複點是p1, p4
            x = x2 + x3 - x1;
            y = y2 + y3 - y1;
        } else if (x2 == x3 && y2 == y3) { // 重複點是p2, p3
            x = x1 + x4 - x2;
            y = y1 + y4 - y2;
        } else if (x2 == x4 && y2 == y4) { // 重複點是p2, p4
            x = x1 + x3 - x2;
            y = y1 + y3 - y2;
        }
        cout << fixed << setprecision(3) << x << " " << y << endl;
    }
    return 0;
}

寫在最後

Cover photo is remixed from @Tiffany, thanks for their work!