아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

랜덤 워크

시간 제한1초메모리 제한128 MB

요약
서로 평행하지 않은 2차원 벡터 n개가 주어질 때, 각 벡터에 부호를 골라 합의 유클리드 길이가 최대가 되도록 한다.
난이도

보통10점 중 7점

유형
기하, 그리디, 정렬, 수학
정답자
아직 제출이 없습니다

문제

랜덤 워크(random walk)는 브라운 운동부터 도박까지 다양한 현상을 모형화하는 데 쓰인다. 예를 들어 동전을 던져 앞면 또는 뒷면에 돈을 거는 도박꾼은 매 턴마다 건 돈을 따거나 잃으며, 시간이 지남에 따라 도박꾼이 가진 돈의 양은 하나의 랜덤 워크가 된다. 매 턴 거는 금액이 다르더라도, 모든 턴을 이기면 가장 많은 돈을, 모든 턴을 지면 가장 적은 돈을 갖게 됨은 쉽게 알 수 있다.

여기서는 다음과 같은 2차원 변형을 생각한다. 서로 평행하지 않은, 0이 아닌 2차원 벡터 nn개 vi=(xi,yi)v_i = (x_i, y_i)가 주어진다. ii번째 단계에서 동전을 던져, 앞면이면 xx 방향으로 xix_i만큼, yy 방향으로 yiy_i만큼 이동하고, 뒷면이면 대신 −xi-x_i, −yi-y_i만큼 이동한다. nn개의 단계를 모두 마치면, 각 εi∈{+1,−1}\varepsilon_i \in \{+1, -1\}에 대해 출발점으로부터의 변위는 ∑i=1nεivi\sum_{i=1}^{n} \varepsilon_i v_i가 된다.

출발점에서 도달할 수 있는 최대 거리, 즉 max⁡ε∈{−1,+1}n∥∑i=1nεivi∥\max_{\varepsilon \in \{-1,+1\}^n} \left\lVert \sum_{i=1}^{n} \varepsilon_i v_i \right\rVert을 구하라. 1차원에서는 쉽지만 2차원에서는 그리 간단하지 않다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 nn (1≤n≤1001 \le n \le 100)이 주어진다. 이어지는 nn개의 줄에는 각각 viv_i를 나타내는 두 정수 xix_i와 yiy_i가 주어지며, 각 좌표의 절댓값은 10001000보다 작다. n=0n = 0인 줄은 입력의 끝을 나타내며 처리하지 않는다.

출력

각 테스트 케이스마다 다음 형식에 정확히 맞추어 한 줄을 출력한다.

Maximum distance = D.DDD meters.

여기서 D.DDD는 출발점으로부터의 최대 거리를 소수점 아래 셋째 자리까지 반올림한 값이다.

예제4

  1. 예제 1

    입력
    3
1 1
0 1
-1 1
2
4 0
1 1
7
1 3
-2 -7
7 8
-2 9
-7 -3
4 -3
-2 -2
0
    예상 출력
    Maximum distance = 3.000 meters.
Maximum distance = 5.099 meters.
Maximum distance = 37.336 meters.

  2. 예제 2

    입력
    1
3 4
0
    예상 출력
    Maximum distance = 5.000 meters.

  3. 예제 3

    입력
    2
1 0
0 1
0
    예상 출력
    Maximum distance = 1.414 meters.

  4. 예제 4

    입력
    1
0 1
2
3 0
0 4
0
    예상 출력
    Maximum distance = 1.000 meters.
Maximum distance = 5.000 meters.