hckim

문제링크

https://www.acmicpc.net/problem/10254

풀이

• 가장 먼 점 두개는 convex hull 을 이루는 점이다.
• rotating calipers 테크닉으로 가장 먼 점이 될 수 있는 후보를 $O(N)$ 에 구한다
  
  1. 초기 캘리퍼스 벡터 =  y 축, 초기 두점 = 가장 왼쪽점(pl)과 가장 오른쪽점(pr)
  2. 볼록 껍질을 회전시킴
  3. 캘리퍼스와 다음으로 만나는 점 중 먼저 바뀌는 점은 직선 pl pl + 1, 과 직선 pr pr + 1 중 캘리퍼스와 각이 더 작은 직선의 점
     1. 벡터 외적으로 구함
  4. 위 과정을 초기 두점 나올때까지 하는데 최대 $O(N)$ 번

코드

• 시간복잡도: $O(NlogN)$
  • (convex hull)

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto ccw = [&](pair<long long , long long >& p1, pair<long long , long long >& p2, pair<long long , long long >& p3) {
        return (p2.first - p1.first) * (p3.second - p2.second) - (p2.second - p1.second) * (p3.first - p2.first);
    };
    auto distSqr = [&](pair<long long , long long >& p1, pair<long long , long long >& p2) {
        return (p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second);
    };
    auto buildConvexHull = [&](vector<pair<long long , long long > >& p) {

        swap(p[0], *min_element(all(p)));
        auto base = p[0];

        auto cmp = [&](pair<long long , long long >& p1, pair<long long , long long >& p2) {
            auto ccw_ = ccw(base, p1, p2);
            if (ccw_ == 0) {
                return distSqr(base, p1) < distSqr(base, p2); 
            }
            return ccw_ > 0;
        };
        sort(all(p), cmp);
        stack<pair<long long , long long > > st;
        st.push(p[0]);
        st.push(p[1]);
        for (int i = 2; i < p.size(); ++i) {
            auto p2 = st.top(); st.pop();
            auto p1 = st.top();
            auto p3 = p[i];
            auto ccw_ = ccw(p1, p2, p3);
            while (ccw_ < 0) {
                p2 = p1;
                st.pop(); p1 = st.top();
                ccw_ = ccw(p1, p2, p3);
            }

            if (ccw_ > 0) {
                st.push(p2);
                st.push(p3);
            } else {
                st.push(p3);
            }
        }
        vector<pair<long long , long long > > convexHull(st.size());
        while (st.size()) {
            convexHull[st.size() - 1] = st.top();
            st.pop();
        }

        return convexHull;
    };

    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;

        vector<pair<long long, long long> > v(N);
        for (auto& e: v) {
            cin >> e.first >> e.second;
        }

        auto ch = buildConvexHull(v);
        auto pl = min_element(all(ch)) - ch.begin();
        auto pr = max_element(all(ch)) - ch.begin();

        pair<int, int> answer = {pl, pr};
        long long tmp = distSqr(ch[pl], ch[pr]);
        int chSize = ch.size();
        for (int i = 0; i < chSize; ++i) {
            pair<long long, long long> v1 = {ch[(pl + 1) % chSize].first - ch[pl].first, ch[(pl + 1) % chSize].second - ch[pl].second};
            pair<long long, long long> v2 = {ch[pr].first - ch[(pr + 1) % chSize].first, ch[pr].second - ch[(pr + 1) % chSize].second};
            if (v1.first * v2.second - v1.second * v2.first > 0) {
                pl = (pl + 1) % chSize;
            } else {
                pr = (pr + 1) % chSize;
            }

            if (tmp < distSqr(ch[pl], ch[pr])) {
                tmp = distSqr(ch[pl], ch[pr]);
                answer = {pl, pr};
            }
        }

        cout << ch[answer.first].first << ' ' << ch[answer.first].second << ' ';
        cout << ch[answer.second].first << ' ' << ch[answer.second].second << '\n';
    }
}

https://www.acmicpc.net/problem/4225

- 다각형이 통과하는데 필요한 최소 슈트 너비는 그 다각형의 점들을 포함하는 볼록 다각형, 즉 convex hull 이 통과하는데 필요한 최소 슈트 너비와 같다

- 볼록 다각형의 한 변이 슈트 한변에 접해서 통과한다고 할 때 필요한 최소 슈트 너비는 그 변에서 가장 멀리 떨어진 점과의 거리와 같다.

1. convex hull 이루는 점 집합 구하기

2. 각 변에 대해서 가장 멀리 떨어진 점까지의 거리들 중 최솟값이 답

  2-1. 변 p1p2 와 점 p3 거리는 외적(p1p2, p2p3)크기 / p1p2길이

  2-2. 올림할 때 소수점 셋째 자리이하가 0 보다 큰지 비교해서 올림하면 틀릴 수 있음, 1e-12 와 비교

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int caseNum = 1;
    int N;

    auto cp = [&](pair<long double, long double> p1, pair<long double, long double> p2, pair<long double, long double> p3) {
        auto ret = (p2.first - p1.first) * (p3.second - p2.second) - (p2.second - p1.second) * (p3.first - p2.first);
        return ret;
    };
    
    pair<long double, long double> base;
    auto cmp = [&](pair<long double, long double> p1, pair<long double, long double> p2) {
        auto cp_ = cp(base, p1, p2);
        if (cp_ != 0) {
            return cp_ > 0;
        }
        return (base.first - p1.first) * (base.first - p1.first) + (base.second - p1.second) * (base.second - p1.second) < (base.first - p2.first) * (base.first - p2.first) + (base.second - p2.second) * (base.second - p2.second);
    };

    while (cin >> N && N) {

        vector<pair<long double, long double> > p(N);
        for (int i = 0; i < N; ++i) {
            cin >> p[i].first >> p[i].second;
        }

        swap(p[0], *min_element(all(p)));

        base = p[0];

        sort(all(p), cmp);

        stack<pair<long double, long double> > st;
        st.push(p[0]);
        st.push(p[1]);
        for (int i = 2; i < N; ++i) {
            auto p2 = st.top(); st.pop();
            auto p1 = st.top();
            auto p3 = p[i];

            auto cp_ = cp(p1, p2, p3);
            while (cp_ < 0) {
                p2 = p1;
                st.pop(); p1 = st.top();
                cp_ = cp(p1, p2, p3);
            }

            if (cp_ > 0) {
                st.push(p2);
                st.push(p3);
            } else {
                //  cp_ = 0
                st.push(p3);
            }
        }

        vector<pair<long double, long double> > convexHull(st.size());
        while (st.size()) {
            convexHull[st.size() - 1] = st.top();
            st.pop();
        }

        long double answer = 1e18;
        
        for (int i = 0; i < convexHull.size(); ++i) {
            auto p1 = convexHull[i];
            auto p2 = convexHull[(i + 1) % (convexHull.size())];
            long double maxDist = 0;
            long double p1p2 = sqrtl((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
            for (int j = 0; j < convexHull.size(); ++j) {
                auto p3 = convexHull[j];
                auto cp_ = abs(cp(p1, p2, p3));
                maxDist = max(maxDist, cp_ / p1p2);
            }
            answer = min(answer, maxDist);
        }

        answer *= 100;
        if (answer - (long long)answer > 1e-12) {
            answer += 1;
            answer = (long long)answer;
        }
        answer /= 100;
        cout.precision(2);
        cout << fixed;
        cout << "Case " << caseNum++ << ": " << answer << '\n';
    }
}