백준 16516 - Lipschitz Constant (C++)

문제 정보

• https://www.acmicpc.net/problem/16516
• 수학, 애드 혹

---

문제 정리

Lipschitz 상수는 다음 식을 만족하는 실수 L의 최소값을 의미한다.

• $|f(x) - f(y)| \leq L \cdot |x-y|$

좌표 N개가 주어질 때, Lipschitz 상수의 값을 구해야 한다.

---

풀이

식을 변형하면 |y증분| / |x증분| <= L이 되고, 이는 두 점간 기울기의 절댓값을 의미한다. L은 두 점 간 기울기 절대값의 최대값을 의미하므로 기울기의 절대값이 최대가 되는 두 점을 찾아야 한다.

기울기가 최대가 되는 두 점은 반드시 붙어있는 두 점일 수밖에 없으므로,

1. x좌표 기준으로 오름차순 정렬.
2. 붙어있는 두 x좌표끼리 기울기의 절대값을 비교해주면 된다.

---

후기

C++로 실수 정밀도 문제는 처음 풀어봤는데 이거 방법을 어딘가에 저장해야 할 것 같다.

---

코드

// 백준 16516

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pld pair<ll, ld>

vector<pld> graph;


ld solve(int N) {
    // x좌표 오름차순 정렬
    sort(graph.begin(), graph.end());

    ll prevX = graph[0].first;
    ld prevY = graph[0].second;
    ld maxL = 0;

    // 바로 인접한 좌표와 기울기 비교
    for (int i=1; i<N; i++) {
        ld curL = abs(graph[i].second-prevY)/abs(graph[i].first-prevX);
        if (curL > maxL)
            maxL = curL;
        prevX = graph[i].first;
        prevY = graph[i].second;
    }

    return maxL;
}


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

    int N;
    cin >> N;

    for (int i=0; i<N; i++) {
        ll a;
        ld b;
        cin >> a >> b;
        graph.push_back({a, b});
    }

    ld ans = solve(N);
    cout << fixed << setprecision(10) << (double)ans << "\n";
}