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

  • 바나나용
    바나나용 
    #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가 나와서 이유가 궁금합니다.
    혹시 제가 작성한 소스에서 동작하지 않는 테스트케이스가 있나요?


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

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


    14년 전 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이 아닌가요? ㅜㅜ
    머가 잘못된건지;;;


    14년 전 link
  • 바나나용
    바나나용

    죄송합니다;;;

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


    14년 전 link

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