alan23273850 的刷題筆記
d135: 00143 - Orchard Trees
Tags: computational-geometry, precision
出處：https://zerojudge.tw/ShowProblem?problemid=d135
提交：https://zerojudge.tw/Submissions?problemid=d135&account=allllllan123456
問題：考慮一塊正方形 $[0,100]\times[0,100]$，其中全部的格子點共 $99^2$ 個都不在邊界上，現在給你三個不彼此重疊的頂點座標 (不限定在格子點上) 皆精準到小數點以下兩位，請問由這些點所形成的三角形區域 (含邊界) 總共覆蓋了幾個格子點？
解法：這題的作法非常單純，因為三角形為凸多邊形，任何一刀割線都不會超出三角形的範圍，所以我們可以在每個 x 坐標上都畫垂直的一刀，如果割線有碰觸到三角形，都必定至少會跟兩條三角形的邊有交點，取這些交點之中的最大 y 座標的無條件捨去，及最小 y 座標的無條件進位，就能分別得到此 x 坐標在該三角形內的最上格子點與最下格子點，兩個高度相減再加一就能得到三角形於該 x 座標上所覆蓋的格子點數量，最後再從 x=1 加總到 x=99 就是答案。真正困難的地方在於實作時精度的處理，讀取座標時不能直接用 double，而是要如程式碼一樣手動讀取後再放大為 100 倍，等於說之後的每個格子點邊長其實也已經跟著變 100 倍，另外比較最上面與最下面格子點的時候也必須以有理數的形式比較，最後如何計算縮小回 1/100 倍的無條件捨去/進位也需要點技巧，頗麻煩的，想要 AC 還是得花點心思。
附註：
[1] http://onlinejudgesolution.blogspot.com/2017/04/uva-solution-143-orchard-trees-solution.html。網路上的作法幾乎都是直接檢查每個格子點有沒有落在三角形上/內，這樣子的作法雖然也是簡單，但是它的效率是跟正方形面積成正比，和我們的作法是跟三角形邊長成正比相較起來實在是差了許多。
1#include <bits/stdc++.h>
2using namespace std;
3
4// Ref: http://onlinejudgesolution.blogspot.com/2017/04/uva-solution-143-orchard-trees-solution.html
5
6typedef pair<int, int> frac, pii, point;
7
8int scaleDouble(char *str) { /* 100 times */
9 int sum = 0, count = INT_MAX;
10 for (int i=0; str[i]; i++)
11 if ('0'<=str[i] && str[i]<='9') {
12 sum = sum*10 + str[i]-'0';
13 if (count <= 2) count--;
14 }
15 else count = 2;
16 if (count == INT_MAX) count = 2;
17 while (count--) sum *= 10;
18 return sum;
19}
20
21// assume p1's x-coordinate <= p2's x-coordinate.
22frac find_height(const point &p1, const point &p2, int x) {
23 if (x < p1.first || p2.first < x) return frac(0,0);
24 return frac(p1.second*(p2.first-x) + p2.second*(x-p1.first), p2.first-p1.first);
25 // 1st int ~ 10^8; 2nd int ~ 10^4.
26}
27
28int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
29 char str[2][7]; int x, y; point arr[3];
30 while (true) {
31 for (int i=0; i<3; i++)
32 cin >> str[0] >> str[1], x = scaleDouble(str[0]), y = scaleDouble(str[1]), arr[i] = point(x, y);
33 if (!arr[0].first && !arr[0].second && !arr[1].first && !arr[1].second && !arr[2].first && !arr[2].second) break;
34 assert(arr[0]!=arr[1] && arr[0]!=arr[2] && arr[1]!=arr[2]);
35 int sum = 0; sort(arr, arr+3); // ensure ascending order of x-coordinates.
36 for (int i=1; i<=99; i++) {
37 frac maX(0,1), miN(10001,1);
38 for (const auto &pii: {pii(0,1), pii(0,2), pii(1,2)}) {
39 frac temp = find_height(arr[pii.first], arr[pii.second], i*100);
40 if (temp.second != 0) { // only if two x-coordinates are different.
41 if ((long long)temp.first * maX.second > (long long)maX.first * temp.second) maX = temp;
42 if ((long long)temp.first * miN.second < (long long)miN.first * temp.second) miN = temp;
43 }
44 }
45 if (miN.first != 10001 * miN.second) // if intersecting (do not use maX!=frac(0,1) since it is a legal value)
46 sum += min(99, maX.first/maX.second/100) - max(1, miN.first/miN.second/100
47 + (miN.first/miN.second%100>0 || miN.first%miN.second>0)) + 1;
48 }
49 cout << setw(4) << sum << '\n';
50 }
51 return 0;
52}