[WA] Arctic 문제

  • Arena
    Arena

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

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

    감사합니다

    #include <stdio.h>
    #include <algorithm>
    #include <stdlib.h>
    #include <math.h>
    #include <vector>
    #include <queue>
    
    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<point> base(numb_base);
        vector<float> dist;
        queue<int> 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;
    }
    

    12년 전
1개의 댓글이 있습니다.
  • Arena
    Arena

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


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