[WA] Arctic 문제

  • User Avatar
    Arena

    안녕하세요,
    AOJ - Arctic 문제를 풀고 있는데
    계속 WA를 맞고 있어서 도움 요청드립니다

    혹시 소스 보시고 반례가 보이시면 알려주세요

    감사합니다
    ~~~ cpp

    #include
    #include
    #include
    #include
    #include
    #include

    using namespace std;

    typedef struct point{
    float x;
    float y;
    }point;

    inline float Dist(point x, point y)
    {
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
    }

    int main()
    {
    int numb_case, numb_base;
    int i, j, pivot;
    int cnt, base_flag[100];
    int numb_dist;
    float ans;
    // freopen("data.txt", "r", stdin);
    scanf("%d",&numb_case);
    while(numb_case--)
    {
    scanf("%d", &numb_base);
    vector base(numb_base);
    vector dist;
    queue temp;

    for(i = 0; i < numb_base; i++)
    {
      scanf("%f %f", &base[i].x, &base[i].y);
    }
    
    if(numb_base == 1 || numb_base == 0)
    {
      printf("%.2f\n", 0.0);
      continue;
    }
    
    // find every edge
    for(i = 0; i < numb_base-1; i++)
    {
      for(j = i+1; j < numb_base; j++)
      {
        dist.push_back(Dist(base[i], base[j]));
      }
    }
    
    // sort 
    sort(dist.begin(), dist.end());
    numb_dist = dist.size();
    
    
    // find min cost
    for(i = 0; i < numb_dist; i++)
    {  
      // init
      cnt = numb_base - 1;
      for(j = 0; j < numb_base; j++)
      {
        base_flag[j] = 0;
      }
    
      temp.push(0);
      base_flag[0] = 1;
    
      while(!temp.empty())
      {
        pivot = temp.front();
        temp.pop();
        for(j = 0;j < numb_base; j++)
        {
          if(base_flag[j] == 0)
          {
            if(Dist(base[pivot], base[j]) < dist[i] || fabs(Dist(base[pivot], base[j]) - dist[i]) <= 0.000000001)
            {
              base_flag[j] = 1;
              cnt--;
              temp.push(j);
            }
          }
        }
      }
    
      if(cnt == 0)
      {
        ans = sqrt(dist[i]);
        break;
      }
    }
    printf("%.2f\n", ans);
    

    }
    return 0;
    }


    14년 전
1개의 댓글이 있습니다.
  • User Avatar
    Arena

    으헝헝헝
    해결했습니다 ㅠㅠ
    도움주신 irc분들 감사드립니다 :)


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