[BOJ 1310] 달리기 코스

문제 링크

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

1310번: 달리기 코스

 

---

아이디어

- 좌표 평면위의 여러 점들 중 가장 먼 거리의 두 점은 convex hull 위에 존재한다

  => convex hull (Graham's scan) 알고리즘

 

- convex hull에서 두 쌍의 연속한 두 점을 잡아 벡터를 만들고

  v1 = p[i+1] - p[i]     ... (p[i], p[i+1])

  v2 = p[j+1] - p[j]     ... (p[j], p[j+1])

  두 벡터의 ccw가 양수인 동안  j값을 증가시켜주며

  음수가 될 때 p[i]와 p[j] 사이의 거리가 최대값 보다 크다면 갱신한다.

=> 회전하는 캘리퍼스 알고리즘

 

회전하는 캘리퍼스의 경우 아래 수도코드로 보면 조금 더 이해가 잘 될 것이다

convex [] ... convex hull을 이루는 점들의 배열
sz = convexHull.size()

fartestDist = 0;
j = 1;

for (int i = 0; i < sz; i++) {
	n_i = (i + 1) % sz;
	for (;;) {
		n_j = (j + 1) % sz;
		px = convex[ni].x - convex[i].x; py = convex[ni].y - convex[i].y
		qx = convex[nj].x - convex[j].x; qy = convex[nj].y - convex[j].y

		if (ccw(px, py, qx, qy) > 0) j = j_next;
		else break;
	}

	dist = distance(convex[i], convex[j]);
	if (dist > fartestDist)
		fartestDist = dist;
}

 

증명은 기회가 되면 다음에 다루도록 하겠다

 

---

주의할 점

본인은 n = 1일 때, 전처리를 안 해주어 여러번 틀렸다

---

소스코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef struct point {
    int x, y, p, q;
    point() : point(0, 0, 0, 0) {};
    point(int x_, int y_, int p_, int q_) : x(x_), y(y_), p(p_), q(q_) {}

    bool operator < (const struct point& z) const {
        if (1LL * q * z.p != 1LL * p * z.q) return 1LL * q * z.p < 1LL * p * z.q;
        if (y != z.y) return y < z.y;
        return x < z.x;
    }
} point;

long long ccw(const int px, const int py, const int qx, const int qy)
{
    return 1LL * px * qy - 1LL * qx * py;
}

long long ccw(const point& p1, const point& p2, const point& p3)
{
    return ccw(p2.x - p1.x, p2.y - p1.y, p3.x - p1.x, p3.y - p1.y);
}

long long dist(const point& p1, const point& p2)
{
    return 1LL * (p1.x - p2.x) * (p1.x - p2.x) + 1LL * (p1.y - p2.y) * (p1.y - p2.y);
}

int main()
{
    int n;
    int st[100001] = { 0 };
    point p[100001];

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        p[i] = point(x, y, 0, 0);
    }

    if (n == 1) {
        puts("0");
        return 0;
    }

    sort(p, p + n);
    for (int i = 1; i < n; ++i) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
    sort(p + 1, p + n);

    // Get ConvexHull using Graham's scan
    st[0] = 0; st[1] = 1;
    int pos = 2;
    for (int i = 2; i < n; ++i) {
        while (pos >= 2 && ccw(p[st[pos - 2]], p[st[pos - 1]], p[i]) <= 0) {
            pos--;
        }
        st[pos] = i;
        pos++;
    }

    // Rotating Calipers
    int j = 1;
    long long ans = 0;
    for (int i = 0; i < pos; ++i) {
        int ni = (i + 1) % pos, nj;
        for (;;) {
            nj = (j + 1) % pos;
            long long ret = ccw(p[st[ni]].x - p[st[i]].x, p[st[ni]].y - p[st[i]].y,
                                p[st[nj]].x - p[st[j]].x, p[st[nj]].y - p[st[j]].y);

            if (ret > 0) j = nj;
            else break;
        }
        if (i != j) {
            long long d = dist(p[st[i]], p[st[j]]);
            if (d > ans) ans = d;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.