RAILGUN문제 질문입니다.

  • Unused
    Unused

    실제 대회장에서 WA를 받았는데 알고리즘 자체는 정답이길래 제출한 코드에서 몇 가지 치명적인 문제를 고치고 추가 조건 넣어서 돌렸는데 계속 오답이 뜹니다. 사용한 알고리즘 & 코드는 다음과 같습니다.

    · 출발점을 0, N개의 액셀러레이터를 1 ~ N, 도착점을 N+1이라고 씁니다. 또 a에서 출발하여 b로 가는 edge를 (a,b) 로 씁니다.

    · 먼저 0과 N+1 사이의 거리가 50보다 큰지 작은지 확인합니다. 작다면 0과 N+1 사이에 다른 점이 일직선으로 놓여있는지 보고 없다면 Yes를 출력합니다. 0과 N+1사이의 거리가 50보다
    크고 N==0이면 No를 출력합니다.

    · 이제 모든 순서쌍 (a, b, c)에 대하여 a-b를 거쳐서 b-c로 갈 수 있는지를 검사합니다. 그 과정은 다음과 같습니다: 먼저 a-b와 b-c 각각의 사이에 다른 점이 없어야 하고, a-b와 b-c간의 거리가 50 이하여야 합니다. 그 후 v1 = b - a, v2 = c - b라고 놓고 v1과 v2를 단위벡터로 바꾼 뒤에, "v2-v1"과
    "b점에 있는 액셀러레이터의 방향"과의 각도가 b점의 기울일 수 있는 각도보다 작거나 같아야 합니다. 만약 v1 = v2라면 액셀러레이터의 방향과 v1 또는 v2와 수직인 벡터와의 각도를 잽니다.

    · edge (0,1), (0,2), ..., (0,N)을 출발점, edge (1,N+1), (2,N+1), ..., (N,N+1)을 도착점으로 하여 BFS를 돌립니다.

    이하는 그걸 구현한 코드입니다.

    #include <stdio.h>
    #include <math.h>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    
    int N;
    
    typedef pair<double,double> point;
    point pt[52], dr[52];
    
    // normeddr[a][b] : (a,b)를 normalize한 벡터
    point normeddr[52][52];
    
    double theta[52];
    double dist[52][52];
    vector<int> vt[3000];
    
    point operator-(point x,point y)
    {
        return point(x.first-y.first, x.second-y.second);
    }
    
    point operator+(point x,point y)
    {
        return point(x.first+y.first, x.second+y.second);
    }
    
    point operator/(point x,double d)
    {
        return point(x.first/d,x.second/d);
    }
    
    double size(point t)
    {
        return sqrt(t.first*t.first+t.second*t.second);
    }
    
    double inner(point x,point y)
    {
        return x.first*y.first + x.second*y.second;
    }
    
    // a, b, c 순서대로 한 직선 위에 놓여있는지 검사
    double isline(int a,int b,int c)
    {
        return fabs(inner(pt[b]-pt[a],pt[b]-pt[c])+dist[a][b]*dist[b][c])<1e-9;
    }
    
    point normalize(point t)
    {
        double size = ::size(t);
        return point(t.first/size, t.second/size);
    }
    
    // edge (x,y)를 고유의 정수로 변환
    int ptoi(int x,int y)
    {
        return x * (N + 2) + y;
    }
    
    // a에서 b를 거쳐 c로 갈 수 있는지 검사
    double reachable(int a,int b,int c)
    {
        if(dist[a][b]>50.0||dist[b][c]>50.0) return false;
        point v1=normeddr[b][a], v2=normeddr[c][b];
        point v3=v1-v2;
        if(size(v3)<1e-9) v3=point(v1.second,-v1.first);
        return acos(fabs(inner(v3,dr[b])/size(v3)))<=theta[b];
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T-- )
        {
            scanf("%d",&N);
            for (int i = 1; i <= N; i++)
            {
                scanf("%lf%lf%lf%lf%lf",&pt[i].first , &pt[i].second , &dr[i].first , &dr[i].second , &theta[i]);
                dr[i]=normalize(dr[i]);
                theta[i]=theta[i]*3.14159265358979323846/180.0+1e-10;
            }
            scanf("%lf%lf%lf%lf",&pt[0].first,&pt[0].second,&pt[N+1].first,&pt[N+1].second);
            dr[0]=dr[N+1]=point(1, 1);
            theta[0]=theta[N+1]=-1;
    
            if(size(pt[0]-pt[N+1])<=50+1e-6)
            {
                int i;
                for (i = 1; i <= N; i++)
                {
                    if (isline(0, i, N+1)) break;
                }
                if(i==N+1)
                {
                    printf("Yes\n");
                    continue;
                }
            }
            else if (N==0)
            {
                printf("No\n");
                continue;
            }
    
            for (int i = 0; i <= N+1 - 1; i++)
            {
                for (int j = i + 1; j <= N+1; j++)
                {
                    dist[i][j] = dist[j][i] = size(pt[i]-pt[j]);
                    normeddr[i][j] = (pt[i]-pt[j]) / dist[i][j];
                    normeddr[j][i] = (pt[j]-pt[i]) / dist[i][j];
                }
            }
    
            for (int i = 0; i <= N+1 - 2; i++)
            {
                for (int j = i + 1; j <= N+1 - 1; j++)
                {
                    for (int k = j + 1; k <= N+1; k++)
                    {
                        if (isline(i,j,k)) dist[i][k]=dist[k][i]=1e99;
                        if (isline(j,k,i)) dist[j][i]=dist[i][j]=1e99;
                        if (isline(k,i,j)) dist[k][j]=dist[j][k]=1e99;
                    }
                }
            }
    
            for (int i = 0; i <= N + 1; i++)
            {
                for (int j = 0; j <= N + 1; j++)
                {
                    if (i == j) continue;
                    for (int k = 0; k <= N + 1; k++)
                    {
                        if (k == i || k == j) continue;
                        if(reachable(i,j,k)) vt[ptoi(i,j)].push_back(ptoi(j,k));
                    }
                }
            }
    
            vector<int> visited(3000,0);
    
            queue<int> que;
            for (int i = 1; i<=N; i++)
            {
                visited[ptoi(i, N+1)] = 2;
            }
    
            for (int i = 1; i<=N; i++)
            {
                visited[ptoi(0, i)] = 1;
                que.push(ptoi(0, i));
            }
    
            while (que.empty() == false)
            {
                int t = que.front();
                que.pop();
    
                for (size_t i = 0; i < vt[t].size(); i++)
                {
                    switch (visited[vt[t][i]])
                    {
                    case 2:
                        printf("Yes\n");
                        goto out;
                    case 0:
                        visited[vt[t][i]]=1;
                        que.push(vt[t][i]);
                        break;
                    }
                }
            }
            printf("No\n");
    
    out:
            for (int i = 0; i <= (N + 2) * (N + 2); i++)
            {
                vt[i].clear();
            }
        }
        return 0;
    }
    

    혹시 알고리즘에 문제가 있는 건가요? 아니면 코드상에 뭔가 제가 놓친 점이 있을까요.. 코드가 좀 지저분해서 죄송합니다.


    9년 전
2개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    일단 봤을때 0 번노드는 액셀러레이터가 아니므로 반사가 일어나지 않아야하는데 isReachable계산하실때보니까 반영되는거같아요~


    9년 전 link
  • Unused
    Unused

    0번노드 N+1번노드에 theta=-1 대입하므로 항상 isReachable에서 false가 리턴됩니다.. ㅠㅠ


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