남극 기지 풀고 있습니다. 도움요청합니다.

  • 바나나용
    바나나용
    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <climits>
    #include <cmath>
    
    using namespace std;
    
    int dis(int a, int b, int x, int y)
    {
      return (x-a)*(x-a) + (y-b)*(y-b);
    }
    
    typedef struct _e {
      int x, y;
    } E;
    
    int main(void)
    {
      int T;
      cin >> T;
    
      while(T--) {
        int N;
        cin >> N;
    
        vector<E> v1, v2;
        E tmp;
        cin >> tmp.x >> tmp.y;  // start position
        v1.push_back(tmp);
    
        int minLen = 0;
    
        for(int i = 0; i < N-1; i++) {
          cin >> tmp.x >> tmp.y;
          v2.push_back(tmp);
        }
    
        while(!v2.empty()) {
          int mmin = INT_MAX;
          vector<E>::iterator it3;
    
          for(vector<E>::iterator it1 = v1.begin(); it1 != v1.end(); it1++) {
            for(vector<E>::iterator it2 = v2.begin(); it2 != v2.end(); it2++) {
              E t1 = *it1;  
              E t2 = *it2;
    
              int d = dis(t1.x, t1.y, t2.x, t2.y);
              cout << d << endl;
              if(mmin > d) {
                mmin = d;
                tmp = t2;
                it3 = it2;
              }
            }
          }
    
          minLen = max(mmin, minLen);
          v1.push_back(tmp);
          v2.erase(it3);
        }
    
        printf("%.2lf\n", sqrt((double)minLen));
      }
    
      return 0;
    }
    

    타임리밋이면 이해가 되는데 계속 wrong answer가 나와서 이유가 궁금합니다.
    혹시 제가 작성한 소스에서 동작하지 않는 테스트케이스가 있나요?


    9년 전
3개의 댓글이 있습니다.
  • A.I
    A.I

    정사각형 윷 놀이 판을 떠올렸을 때, 귀퉁이 어느 한 점이 start position인 케이스가 반례가 될 수 있다고 봅니다. :D


    9년 전 link
  • 바나나용
    바나나용

    제가 만든 테스트 케이스 돌렸을 때, 아래와 같이 나왔습니다.

    4
    5
    0 0
    1 0
    1 1
    1 2
    0 2
    6
    1 1
    17 39
    4 7
    6 21
    5 11
    3 11
    9
    0 0
    1000 1000
    0 1000
    1000 0
    500 500
    7 3
    7 3
    7 3
    7 3
    45
    0 8
    0 1
    0 2
    0 3
    0 4
    0 5
    0 6
    0 7
    0 0
    1 0
    1 1
    1 7
    1 8
    2 0
    2 2
    2 6
    2 8
    3 0
    3 3
    3 5
    3 8
    4 0
    4 4
    4 4
    4 8
    5 0
    5 3
    5 5
    5 8
    6 0
    6 2
    6 6
    6 8
    7 0
    7 1
    7 7
    7 8
    8 0
    8 1
    8 2
    8 3
    8 4
    8 5
    8 6
    8 7
    8 8

    출력결과

    1.00
    21.10
    707.11
    1.41

    마지막 케이스는
    1 1 1 1 1 1 1 1 1
    1 1 0 0 0 0 0 1 1
    1 0 1 0 0 0 1 0 1
    1 0 0 1 0 1 0 0 1
    1 0 0 0 1 0 0 0 1
    1 0 0 1 0 1 0 0 1
    1 0 1 0 0 0 1 0 1
    1 1 0 0 0 0 0 1 !
    1 1 1 1 1 1 1 1 1
    인 경우인데 1.41이 아닌가요? ㅜㅜ
    머가 잘못된건지;;;


    9년 전 link
  • 바나나용
    바나나용

    죄송합니다;;;

    실수인데... int로 받아서 문제가 생겼네요 ㅜㅜ


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.