Peienwu's Blog

Hello world

0%

[題解]TIOJ 1105 H.PS3

發表於 分類於 Valine：
文章字數： 4.1k 所需閱讀時間 ≈ 4 分鐘

TIOJ 1105 H.PS3

題目連結
Submission $O(n^2)$
Submission $O(n\log n)$

題目敘述
給你平面上N個點（N≤3000），請求出最遠點對的索引值（小的在前、大的在後）

我做了一份最近點對：不同複雜度之解決方式的筆記，共有四種方法可以解決那個問題，這一題要求的是最遠點對，作法與最近點對其實差蠻遠的。由上幾題知道凸包的求法，因為凸包是可以圍住所有點的多邊形，因此最遠點對也應該在凸包上，而且所在的位置會為在凸包的兩側上（如果不落在凸包上，一定可以把點向兩側延伸到凸包上，且移動過後的點對距離一定比原始的點對距離大）。

找完凸包之後，可以用旋轉卡尺的方式尋找最遠點對。想像兩條平行線中間夾著凸包，逆時鐘旋轉繞行凸包一圈，過程不斷更新最遠點對的距離。在實作上兩條平行線可以被想像成由 $Pi$ 指向 $P{i+1}$ 的向量，透過外積三角形面積公式決定卡尺該如何移動。

以下圖為例，我們要找 $\overline{HM}$ 為底可以形成的最大三角形面積的頂點，因為在同底的情況下面積就代表點與邊的垂直距離，最大的垂直距離意味著這條底邊可以垂直延伸的最遠距離。因為凸包必定是凸多邊形，因此三角形的面積會呈現單峰函數，因此只需要從下一個三角形面積的大小，決定雙指針中比較快的指標的移動情況。

如果仔細來看，以下圖為例，當前較快的指標指向的位置是 $D$ 點，考慮一條與與 $\overline{HM}$ 平行的直線，若下一個點 $J$ 在平行線段的另外一側，則將指標移往 $J$ 點。可能會有一個疑問，如果比較下圖的線段長度，會發現到 $\overline{DH}$ 的長度比經過 $J$ 點的兩條線段都還要長，那為何還要更新至 $J$ 點？舉這個例子不太好，不過可以想像當旋轉卡尺轉到以 $\overline{FH}$ 為底的時候，會將最遠點對的距離更新成 $\overline{HD}$ 的長度。如果今天 $H$ 的左側又多加了一個新點 $P$，則最遠點對會變成 $\overline{PD}$ 的距離。

簡單來說，最遠點對一定會發生對角的凸包點上面，即使現在以 $\overline{HM}$ 為底最遠點並非 $J$ 而是 $D$ ，但在旋轉卡尺旋轉到 $\overline{FH}$ 時就能將距離更新成 $\overline{HD}$ 的距離。

實作小細節

這一題有點麻煩，因為他要輸出的是最遠點對的索引值，而不是最遠點對之間的距離。在尋找凸包的過程中，會對所有點進行排序，因此原有的索引值順序會被打亂，需要在一開始輸入的時後就好好維護每一個座標的索引值。

以下是AC Code：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define pdd pair<double,double>
#define int long long
#define ll long long
#define ld long double
#define N 100001
#define all(x) x.begin(),x.end()
#define eps 1e-9
#define x first
#define y second

using namespace std;

struct pt{
    int x,y,ind;
    bool operator < (pt b){
        if(x == b.x)return y < b.y;
        return x < b.x;
    }
    bool operator > (pt b){
        if(x == b.x)return y > b.y;
        return x > b.x;
    }
    bool operator == (pt b){
        if(x-b.x == 0 && y-b.y == 0)return true;
        return false;
    }
    pt operator+(pt b) {return {x + b.x, y + b.y};} //向量相加
    pt operator-(pt b) {return {x - b.x, y - b.y};} //向量相減
    int operator^(pt b) {return x * b.y - y * b.x;} //向量外積cross
    int operator*(pt b) {return x * b.x + y * b.y;} //向量內積dot
    int dis() {return x*x + y*y;}
};

vector<pt> p,hull;
pt pt_ans;
int n,h;

bool check(pt a, pt b, pt o){
    pt aa = a - o;
    pt bb = b - o;
    return (aa ^ bb) >= 0;
}

bool check2(pt a,pt b,pt c,pt d){
    int aa = abs((a - c)^(b - c));
    int bb = abs((a - d)^(b - d));
    return aa < bb;
}

bool cmp(pt a, pt b){
    if(a == b)return a.ind < b.ind;
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}

void convex_hull(){
    stable_sort(all(p),cmp);
    rep(i,0,n-2)if(p[i] == p[i+1])p[i+1].ind = p[i].ind;
    hull.clear();
    for(auto i : p){
        while(hull.size() > 1 && check(i,hull[hull.size()-1],hull[hull.size()-2]))
            hull.pop_back();
        hull.push_back(i);
    }
    int sz = hull.size();
    h = hull.size()-1;
    hull.pop_back();
    reverse(all(p));
    for(auto i : p){
        while(hull.size() > sz && check(i,hull[hull.size()-1],hull[hull.size()-2]))
            hull.pop_back();
        hull.push_back(i);
    }
    hull.pop_back();
}

void solve(){
    int ans = 0,d = h,sz = hull.size();
    rep(i,0,sz-1){
        while(check2(hull[i],hull[(i+1)%sz],hull[d],hull[(d+1)%sz]))
            d = (d+1)%sz;
        if(ans < (hull[i]-hull[d]).dis()){
            ans = (hull[i]-hull[d]).dis();
            int a = hull[i].ind,b = hull[d].ind;if(a > b)swap(a,b);
            pt_ans = {a,b};
        }
        else if(ans == (hull[i]-hull[d]).dis()){
            int a = hull[i].ind,b = hull[d].ind;if(a > b)swap(a,b);
            if(pt_ans > (pt){a,b})pt_ans = {a,b};
        }
        if(ans < (hull[(i+1)%sz]-hull[d]).dis()){
            ans = (hull[(i+1)%sz]-hull[d]).dis();
            int a = hull[(i+1)%sz].ind,b = hull[d].ind;if(a > b)swap(a,b);
            pt_ans = {a,b};
        }
        else if(ans == (hull[(i+1)%sz]-hull[d]).dis()){
            int a = hull[(i+1)%sz].ind,b = hull[d].ind;if(a > b)swap(a,b);
            if(pt_ans > (pt){a,b})pt_ans = {a,b};
        }
    }
}

signed main(){
    Orz;
    while(cin>>n){
        if(n == 0)break;
        pt_ans = (pt){0,0};
        p.resize(n,{0,0});
        rep(i,0,n-1){
            cin>>p[i].x>>p[i].y;
            p[i].ind = i;
        }
        convex_hull();
        solve();
        cout<<pt_ans.x<<" "<<pt_ans.y<<endl;
    }
}

/*
5
9 1
1 5
1 2
9 9
5 1
 */