하늘에서 정의가 빗발친다!

2017-01-09 05:02:15 | 조회수 914



※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


규현이의 파라는 항상 원점(0,0) 에 위치하고, 로봇은 임의의 좌표 x,y에 위치합니다.


이 문제를 풀기 위해서는 먼저 규현이와 파라 로봇의 거리를 알아야 합니다.


두 점 X(x1,x2), Y(y1,y2)의 좌표를 알고 있을 때, 거리는 다음과 같은 식으로 구할 수 있습니다.


$dist(X,Y) = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$


여기서 제곱의 경우는 뺄셈한 수를 2번 곱하는 걸로 구현을 할 수 있는데, 루트는 어떻게 계산해야 할까요?


바로 <cmath> 라이브러리에서 제공하는 sqrt 함수를 통해 계산할 수 있습니다.


(sqrt 사용법은 소스코드를 참조하세요.)


연산을 한 후 그 값을 미사일의 속도로 나누면 정답을 구할 수 있습니다.



제공된 2개의 소스 코드 중, 1번째 소스코드에서는 위와 같은 연산을 한 후, 로봇의 번호를 쉽게 출력하기 위해 로봇을 class로 구현하였습니다.

이 때 중요한 것은 로봇의 번호를 출력하기 위해 정렬이 필요한 부분을 연산자 오버로딩으로 구현하였다는 점입니다.

연산자 오버로딩에 대해 더 자세히 알아보고 싶다면, STEPS bar를 이용하시면 됩니다.


또 중간에 보이는 for(auto i : v) 가 매우 생소하신 분도 있을 겁니다.

auto 연산자와 range based for loop 역시 STEPS bar를 이용하시면 됩니다.



※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

struct Node
{
    int no, x, y, v;
    double tm;
    Node(int a, int b, int c, int d) { no = a, x = b, y = c, v = d; }
    bool operator < (const Node & n)const
    {
        return tm == n.tm ? no < n.no : tm < n.tm;
    }
};
int main()
{
    vector<Node> v;
    int n;
    double d = 1000000000;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v.push_back({ i + 1,a,b,c });
        v[i].tm = sqrt(a*a + b*b) / c;
    }
    sort(v.begin(), v.end());
    for (auto i : v) cout << i.no << "\n";
}

//2번째 소스(class를 사용하지 않은 소스)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N;
    scanf("%d",&N);
    vector<pair<double, int>> aa;
    for(int i=1;i<=N;i++){
        double x,y,v,t;
        scanf("%lf %lf %lf",&x,&y,&v);
        t = ((x*x) + (y*y)) / (v*v);
        aa.push_back(make_pair(t,i));
    }
    sort(aa.begin(),aa.end());
    for(int i=0;i<N;i++){
        printf("%d\n",aa[i].second);
    }
}


하늘에서 정의가 빗발친다! - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글