[c++] BOJ 1393번 :: 음하철도 구구팔 (코드, 주의할 점, 테스트케이스)

음하철도 구구팔

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	445	64	57	29.082%

문제

최백준은 음하철도 구구팔에 탔다.

문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다.

그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다.

그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다.

어디서 뛰어내려야 하는가?

입력

첫째 줄에는 정류장의 위치 x y가 주어지고, 둘째 줄에는 현재 열차의 위치 X Y와 열차가 초마다 이동하는 x좌표 y좌표가 주어진다. 열차는 항상 직선으로 움직인다.

주어지는 모든 수는 -100이상, 100이하의 정수이다.

출력

최백준이 뛰어내리는 위치를 출력한다. 정답은 항상 정수이다.

 

주의 할 점

• 1초 단위로 뛰어내릴 수 있는 것이 아니다.
• 기차는 한 방향으로만 간다.

 

나의 답

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int x_pt, y_pt, X, Y, del_x, del_y;
double dist;
pair<int, int> near_point;


double getDistance(int x, int y) {
    double tmp = pow((x - x_pt), 2) + pow((y - y_pt), 2);
    return tmp;
}


void findNearDist() {
    double x = X; double y = Y;
    while (1) {
        x += del_x;
        y += del_y;

        double tmp = getDistance(x, y);
        if (tmp > dist) { // 거리가 증가했으면
            break;
        }
        else {
            dist = tmp;
            near_point.first = x; near_point.second = y;
        }
    }

}

void fixDel() {
    int small = min(del_x, del_y);

    // 둘 중 하나가 0이면 나머지는 1 (중요!)
    if (small == 0) {
        if (del_x == 0)
            del_y = 1;
        else
            del_x = 1;
        return;
    }

    // 둘 다 0이 아니면 최대공약수로 나눠주기
    while (small) {
        if (del_x%small == 0 && del_y%small == 0) {
            break;
        }else
            small--;
    }

    if (small > 1) {
        del_x /= small; del_y /= small;
    }
}

int main() {
    cin >> x_pt >> y_pt;
    cin >> X >> Y >> del_x >> del_y;

    dist = getDistance(X, Y); // 첫번째 위치에서의 거리
    near_point.first = X; near_point.second = Y;

    fixDel();
    if(del_x!=0 || del_y!=0)
        findNearDist();

    // 둘다 0이면 그냥 출력
    cout << near_point.first << " " << near_point.second;
}

테스트케이스

100 102
0 0 0 0
=> 0 0

5 2
2 1 2 4
=> 3 3

5 2
2 1 1 1
=> 4 3

50 72
0 0 7 3
=> 70 30

50 72
0 0 0 4
=> 0 72

50 72
0 0 4 0
=> 50 0

 

다른 답

brute force로도 풀 수 있다.