louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=50120

題目大意:  給你一個陣列，有1代表有點，計算點之間最長距離

思路:  枚舉會超時，這題不是稀疏圖，用凸包包一圈，再計算枚舉凸包上的點。

凸包演算法使用Graham，用最左下角當作原點，計算每個點向量，逆時針極角排序，然後開始縮點。

蠻不錯的題目，讓我學到凸包，蠻喜歡這題的。

代碼:  

#include <bits/stdc++.h>
#define M 7050
#define N 105
using namespace std;

struct P{
    int x, y;
}p[M * N];

double dis(P a, P b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

//右手定則，大於0，代表oa到ob逆時針
int cross(P o, P a, P b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

//排序依據逆時針，且距離較短者
bool cmp(P a, P b)
{
    int x = cross(p[0], a, b);
    return x > 0 || (x == 0 && dis(a, p[0]) < dis(b, p[0]));
}

vector<P> Graham(int n){
    vector<P> stk(n);
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k > 1 && (cross(p[i], stk[k-2], stk[k-1])) <= 0) //縮點
            k--;
        stk[k++] = p[i];
    }
    stk.resize(k);
    return stk;
}

int main()
{
    int n, m;
    while(cin >> n >> m){
        int id = 0, md = 0;
        P mn = {M, M};
        for(int i = m; i >= 1; --i){
            for(int j = 1; j <= n; ++j){
                char x;
                cin >> x;
                if(x == '0') continue;
                p[id++] = {j, i};
                if(mn.y > p[id - 1].y || (mn.y == p[id - 1].y && mn.x > p[id - 1].x)){ //找出最左下角
                    mn = p[id - 1];
                    md = id - 1;
                }
            }
        }

        swap(p[md], p[0]); //把最小點當原點
        sort(p + 1, p + id, cmp);

        vector<P> hull = Graham(id);

        double ans = 0;
        for(int i = 0; i < hull.size(); ++i){
            for(int j = i + 1; j < hull.size(); ++j){
                ans = max(ans, dis(hull[i], hull[j]));
            }
        }

        printf("%.0f\n", ans);
    }
    return 0;
}
/*
5 6
00000
10001
01110
01110
00100
01100
*/