[백준] 10640 : Rings

https://www.acmicpc.net/problem/10640

문제 분석

 이번 문제는 3차원 공간에서 반지름이 1인 두 원이 주어졌을 때 두 원이 체인을 이루는 지를 물어보는 문제이다. 체인을 이룬다는 것은 두원이 서로 분리가 안되게끔 사슬처럼 얽혀있는 상태를 의미한다. 이때, 두원이 체인을 이루는 조건을  판별하는 것이 문제의 핵심이다.

 체인을 이룬다는 것은 어떤 한 원의 일부가 다른 원의 내부에 존재한다는 특징을 가진다. 또한, 이러한 특징을 두 원 중 어떤 원을 기준으로 해도 성립해야 한다. 즉, 서로가 서로의 일부를 원 내부에 포함해야 한다. 어떤 원 내부의 점은 어떤 원을 이루는 평면과 다른 원의 두 교점이 될수 밖에 없다. 결국 어떤 원을 이루는 평면과 다른 원의 교점 중 하나가 어떤원내부에 존재해야하고, 이 조건을  두 원 간에 상호적으로 만족하는 것이 체인을 이루는 조건이다.  

 이러한 원 내부의 점들은 한가지 특징이 있다. 두 원을 이루는 평면의 교선 상에 존재한다는 것이다. 즉, 교선상의 원과 만나는 점들이 서로 교차하게끔 존재하는지를 확인하면 두원이 체인을 이루는 지를 확인가능하다. 이때, 교선과 원 사이에 교점이 없으면 자연스럽게 체인을 못 이루는 상황이다.

 마지막으로 정리하면 다음과 같다.

1. 두 평면사이의 교선을 구한다.
   1. 교선이 없으면 False
2. 교선과 원 사이의 교점을 구한다.
   1. 교점이 없으면 False
3. 구해진 교점의 관계를 구한다.
   1. 두 원의 교점들이 서로 교차하지않으면 False 
   2. 어떤 한 원의 교점들을 다른원이 포함하면 False
   3. 서로 교차해서 존재하면 False

문제 해결 전략

 교선을 구하기 위해서는 두 평면의 법선벡터를 외적 하여 직선의 방향벡터를 구하고 평면 위를 지나는 한 점을 구하여 $x+td$의 형태로 매개변수 $t$로 직선을 표현한다.

 교선과 원사이의 교점은 직선의 방정식 $p=x+td$ 과 구의 방정식  $|p-c|=r^2$의 연립방정식을 통하여 구한다. 이떄, 실제 좌표대신 t의 값만으로도 교차여부를 판별가능하니 해당 값만 구한다.

 교차 여부는 모든 교점들의 최대 거리가 두 원의 교점거리 중 큰 값보다 크고 $($ 3-2 배제$)$, 두 원의 교점거리의합보다 작은지$($3-1 배제 $)$ 를 보고 판단한다.

코드

#include <iostream>
#include <math.h>
#include <stdexcept>

using namespace std;

float center1[3],center2[3];
float n1[3],n2[3],d[3];
float v1[3],v2[3];
float w1[3],w2[3];

int GetIntersectionPoints(float linestart[3], float center[3], float d[3], pair<float,float>& out)
{
    float A=1.0f;
    float B = d[0]*(linestart[0]-center[0])+d[1]*(linestart[1]-center[1])+d[2]*(linestart[2]-center[2]);
    float C = (linestart[0]-center[0])*(linestart[0]-center[0])+(linestart[1]-center[1])*(linestart[1]-center[1])+(linestart[2]-center[2])*(linestart[2]-center[2])-1;
    float Delta = B*B-A*C;
    float sqrtDelta = sqrtf(Delta);
    if (Delta>0){
        out=make_pair(-B-sqrtDelta,-B+sqrtDelta);
        return 1;
    }
    else{
        return 0;
    }
}

int IsChained(pair<float,float> points1,pair<float,float> points2)
{
    float dist1=fabsf(points1.first-points1.second);
    float dist2=fabsf(points2.first-points2.second);
    float minv=min(min(points1.first,points1.second),min(points2.first,points2.second));
    float maxv=max(max(points1.first,points1.second),max(points2.first,points2.second));
    float dist= maxv-minv;
    if (dist>max(dist1,dist2) && dist<dist1+dist2){
        return 1;
    }
    return 0;
}

int main()
{
    cin >> center1[0] >> center1[1] >> center1[2];
    cin >> v1[0] >> v1[1] >> v1[2];
    cin >> w1[0] >> w1[1] >> w1[2];

    cin >> center2[0] >> center2[1] >> center2[2];
    cin >> v2[0] >> v2[1] >> v2[2];
    cin >> w2[0] >> w2[1] >> w2[2];

    //평면1의 법선 벡터
    n1[0]=v1[1]*w1[2]-v1[2]*w1[1];
    n1[1]=-v1[0]*w1[2]+v1[2]*w1[0];
    n1[2]=v1[0]*w1[1]-v1[1]*w1[0];
    //평면2의 법선 벡터
    n2[0]=v2[1]*w2[2]-v2[2]*w2[1];
    n2[1]=-v2[0]*w2[2]+v2[2]*w2[0];
    n2[2]=v2[0]*w2[1]-v2[1]*w2[0];
    //직선의 방향 벡터
    d[0]=n1[1]*n2[2]-n1[2]*n2[1];
    d[1]=-n1[0]*n2[2]+n1[2]*n2[0];
    d[2]=n1[0]*n2[1]-n1[1]*n2[0];
    float templ=sqrtf(d[0]*d[0]+d[1]*d[1]+d[2]*d[2]);
    d[0]/=templ;
    d[1]/=templ;
    d[2]/=templ;

    float lineStart[3]={0.0f, 0.0f, 0.0f};

    float A1 = n1[0], B1 = n1[1], C1 = n1[2];
    float D1 = n1[0] * center1[0] + n1[1] * center1[1] + n1[2] * center1[2];
    float A2 = n2[0], B2 = n2[1], C2 = n2[2];
    float D2 = n2[0] * center2[0] + n2[1] * center2[1] + n2[2] * center2[2];
    
    //직선의 한 점
    float det=0.0f;
    det=A1 * B2 - A2 * B1;
    if (fabsf(det)>1e-6) 
    {
        lineStart[0] = (D1 * B2 - D2 * B1) / det;
        lineStart[1] = (D2 * A1 - D1 * A2) / det;
    } 
    else
    {
        det=A1 * C2 - A2 * C1;
        if (fabsf(det)>1e-6) 
        { 
            lineStart[0] = (D1 * C2 - D2 * C1) / det;
            lineStart[2] = (D2 * A1 - D1 * A2) / det;
        }
        else
        {
            det=B1 * C2 - C1 * B2;
            if (fabsf(det)>1e-6)
            {
                lineStart[1] = (D1 * C2 - D2 * C1) / det;
                lineStart[2] = (D2 * B1 - D1 * B2) / det;
            }
            else
            {
                cout << "NO" << "\n";
                return 0;
            }
        }
    } 
    

    pair<float,float> pPair1, pPair2;
    if (!GetIntersectionPoints(lineStart, center1, d,  pPair1)){
        cout << "NO" << "\n";
        return 0;
    }
    if (!GetIntersectionPoints(lineStart, center2, d,  pPair2)){
        cout << "NO" << "\n";
        return 0;
    }
    if (IsChained(pPair1, pPair2))
    {
        cout << "YES" << "\n";
        return 0;
    }
    else{
        cout << "NO" << "\n";
        return 0;
    }
}