algospot.com :: 질문과 답변: RAILGUN문제 질문입니다.

RAILGUN문제 질문입니다.

실제 대회장에서 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;
}

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

11년 전

2개의 댓글이 있습니다.

Kureyo

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

11년 전 link
Unused

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

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

SINCE 2007

다가오는 이벤트들

RAILGUN문제 질문입니다.

2개의 댓글이 있습니다.