무대에서 떨어질 수 있는 거리로 파라메트릭 서치를 하면 되고,
중요한 건 거리가 정해지면 놓을 수 있는 위치도 O(M)개로 줄어든다는 거임


1. 시작점 (물론 거리 밑에 있다면)
2. 끝점 (이하 동일)
3. 거리 직선과의 교점
4. 거리 안에 있는 곳 중에서 ^


그리고 이 점들을 모두 찾으면 그냥 되는지 해보면 됨
이건 현재까지 비춘 곳의 x좌표가 np라면 X - Y <= np인 가장 뒷점을 찾아서 땅에 비추면 됨


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#include <iostream> #include <algorithm> constexpr int MAXM = 200'004; int N, M, L; struct { long long x, y; } line[MAXM]; long long lxy[MAXM]; struct { long long x, y; } K[MAXM]; int Kcnt; bool solvem(const long long th) { Kcnt = 0; if (line[0].y <= th) K[Kcnt++] = {line[0].x, line[0].y}; for (int i = 1; i < M; ++i) { if (th > line[i - 1].y && line[i - 1].y > line[i].y) K[Kcnt++] = {line[i - 1].x, line[i - 1].y}; if (line[i - 1].y < th && th <= line[i].y) { K[Kcnt++] = {line[i - 1].x + (th - line[i - 1].y), th}; } if (line[i].y <= th && th < line[i - 1].y) { K[Kcnt++] = {line[i - 1].x + (line[i - 1].y - th), th}; } } if (line[M - 1].y <= th) K[Kcnt++] = {line[M - 1].x, line[M - 1].y}; long long np = 0; int lx = 0; for (int i = 0; i < L && np < N; ++i) { for (; lx < Kcnt; ++lx) { if (K[lx].x - K[lx].y > np) break; } np = K[lx - 1].x + K[lx - 1].y; } return (np >= N); } long long solve() { long long l = 2'000'000'000'000, r = 0, ans = -1; for (int i = 0; i < M; ++i) { line[i].x <<= 1; line[i].y <<= 1; lxy[i] = line[i].x - line[i].y; r = std::max(r, line[i].y); l = std::min(l, line[i].y); } N <<= 1; while (l <= r) { const long long m = l + (r - l) / 2; if (solvem(m)) { ans = m; r = m - 1; } else { l = m + 1; } } return ans; } int main() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; for (int t = 1; t <= tc; ++t) { cin >> N >> M >> L; int last = 0; cin >> line[0].x >> line[0].y; for (int i = 1; i <= M; ++i) { cin >> line[i].x >> line[i].y; const int d = (line[i].y > line[i - 1].y ? +1 : -1); if (last == d) { --M; line[i - 1] = line[i]; --i; } else last = d; } ++M; const long long ans = solve(); cout << "Case #" << t << '\n'; if (ans == -1) cout << "-1\n"; else if (ans % 2) cout << ans << " 2\n"; else cout << (ans / 2) << " 1\n"; } }