SCPC 2019 1차예선 5번 구현 소스 코드

SCPC 2019 1차예선 5번. 세포 키우기의 소스 코드입니다.

5번 소스 코드 요청이 많아서 공개합니다.

 

선분 조각을 합치려면 우선 선분을 \(x\)좌표 순으로 정렬해 갖고 있어야 합니다.

그렇게 갖고 있다면, 합치려는 두 그래프에서 왼쪽 것부터 각각 빼낸 다음, 둘 중에 작은 걸 택하면 됩니다.

두 선분 조각 중 어느 하나가 다른 하나보다 완전히 밑에 있으면 그냥 하나를 버리면 되고요, 그렇지 않다면 선분을 조각내 줍니다. 이때 선분은 좌표를 미리 2배로 해 주었기 때문에 정수점이 아닌 곳에서 만나는 일은 없다고 생각했어요.

 

편하게 구현하려고 deque를 사용했어요. 쌩 자료구조보다 좀 느리긴 해도 여전히 amortized \(O(1)\)이라서요.

구현 아이디어 설명은 https://paido.tistory.com/14를 참고해주세요.

 

궁금하신 점 있으면 댓글로 질문 주세요. 그럼 이만~

 

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
 
long long ReadLong();
 
 
int N;
long long L, R;
struct Point {
    long long x, y;
};
std::vector<Point> pts;
 
void ReadInput() {
    L = ReadLong() * 2;
    R = ReadLong() * 2;
    N = (int)ReadLong();
 
    pts.clear();
    for (long long i = 0; i < N; i++) {
        Point p;
        p.x = ReadLong() * 2;
        p.y = std::abs(ReadLong()) * 2;
        pts.push_back(p);
    }
}
 
struct Segment {
    long long L;
    long long R;
    long long LY;
    long long Slope; // One of -1, 0, 1
 
    long long RY() {
        return LY + (R - L) * Slope;
    }
};
 
std::deque<Segment> ComputeSegments(int p_start, int p_end) {
    std::deque<Segment> result;
    Segment s;
 
    /* base case: n = 1 */
    if (p_start == p_end) {
        Point &p = pts[p_start];
        long long xmy = p.x - p.y;
        long long xpy = p.x + p.y;
 
        if (xmy > L) {
            s.L = L;
            s.R = std::min(xmy, R);
            s.LY = p.x - s.L;
            s.Slope = -1;
            result.push_back(s);
        }
        if (xmy < R && xpy > L) {
            s.L = std::max(xmy, L);
            s.R = std::min(xpy, R);
            s.LY = p.y;
            s.Slope = 0;
            result.push_back(s);
        }
        if (xpy < R) {
            s.L = std::max(xpy, L);
            s.R = R;
            s.LY = s.L - p.x;
            s.Slope = +1;
            result.push_back(s);
        }
 
        return result;
    }
 
    /* inductive case: merging */
    int p_mid = (p_start + p_end) / 2;
    std::deque<Segment> lefts = ComputeSegments(p_start, p_mid);
    std::deque<Segment> rights = ComputeSegments(p_mid + 1, p_end);
 
    while (!lefts.empty() && !rights.empty()) {
        Segment a = lefts.front();
        Segment b = rights.front();
 
        /* equalize segment length */
        if (a.R > b.R) {
            s.L = b.R;
            s.R = a.R;
            s.LY = a.LY + a.Slope * (s.L - a.L);
            s.Slope = a.Slope;
            lefts.pop_front();
            lefts.push_front(s);
            rights.pop_front();
 
            a.R = b.R;
        }
        else if (a.R < b.R) {
            s.L = a.R;
            s.R = b.R;
            s.LY = b.LY + b.Slope * (s.L - b.L);
            s.Slope = b.Slope;
            lefts.pop_front();
            rights.pop_front();
            rights.push_front(s);
 
            b.R = a.R;
        }
        else {
            lefts.pop_front();
            rights.pop_front();
        }
 
        /* process intersection */
        long long aLY = a.LY;
        long long bLY = b.LY;
        long long aRY = a.LY + a.Slope * (a.R - a.L);
        long long bRY = b.LY + b.Slope * (b.R - b.L);
 
        if (aLY <= bLY && aRY <= bRY) {
            result.push_back(a);
        }
        else if (aLY >= bLY && aRY >= bRY) {
            result.push_back(b);
        }
        else {
            /* intersection within interval */
            long long x = a.L - (bLY - aLY) / (b.Slope - a.Slope);
 
            s.L = a.L;
            s.R = x;
            s.Slope = (aLY < bLY) ? a.Slope : b.Slope;
            s.LY = (aLY < bLY) ? aLY : bLY;
            result.push_back(s);
 
            s.L = x;
            s.R = b.R;
            s.Slope = (aLY < bLY) ? b.Slope : a.Slope;
            s.LY = a.LY + (x - a.L) * a.Slope;
            result.push_back(s);
        }
    }
 
    return result;
}
 
 
void ComputeAnswer() {
    std::deque<Segment> segs = ComputeSegments(0, N - 1);
    long long opt = 0;
    for (auto &s : segs) {
        opt = std::max(opt, s.LY);
        opt = std::max(opt, s.RY());
    }
    printf("%lld\n", opt);
}
 
int main() {
    long long T = ReadLong();
 
    for (long long test_case = 1; test_case <= T; test_case++) {
        ReadInput();
        printf("Case #%lld\n", test_case);
        ComputeAnswer();
    }
    return 0;
}
 
long long ReadLong() {
    long long p;
    scanf("%lld", &p);
    return p;
}