강의실/정보영재

https://wondangcom.com/903

 

(기하알고리즘) 반직선의 교점 찾기 1

지난번에 두 선분의 교점 찾기에 대해 설명을 해 드린적이 있는데요. https://wondangcom.com/466 기하알고리즘] 두 선분의 교차점 찾기 위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다. 이..

wondangcom.com

지난번에 반직선의 교점 찾기 위해서 기본적인 클래스를 구현해 보았는데요.

오늘은 지난번에 만들어 놓은 클래스와 함수들을 이용해서 다음의 문제를 풀어 보도록 하겠습니다.

문제 원본 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2555&sca=30d0

 

JUNGOL | 반직선이 만나는 경우의 수 > 문제은행

제한시간: 1000 ms    메모리제한: 128 MB 해결횟수: 8 회    시도횟수: 38 회    N개의 반직선이 2차원 평면에 주어진다. 반직선의 시작점은 0초과 L미만의 정수값을 갖는다. N개의 반직선중에 임의의 두 반직선이 만나는 경우의 수를 구하라. N개의 반직선의 시작점은 모두 다르다. 각 반직선은 시작점과 움직이는 방향점으로 표현된다. 두 반직선이 만나는 경우 만나는 점이(0, 0) ~ (L, L)에 위치한 경우만 유효한 것으로 간주한다.

jungol.co.kr

이미지 출처 : jungol.co.kr

위의 그림과 같이 반직선의 만나는 위치의 갯수가 15개인것을 찾는 문제인데요.

입력 데이터는 다음과 같이 들어 옵니다.

 

먼저 교점을 찾는 함수를 구현해 보도록 하겠습니다.

위의 함수에서 만약에 기울기가 같은 경우를 처리 했는데요.

기울기가 같은데 같은 직선이 아니라면 평행 한 것이므로 교점이 존재하지 않게 됩니다.

같은 직선에 대해서만 처리했는데요...  수직선인 경우에는 y축만 가지고 판단을 하면 되는데요...

방향이 같은 방향이라면 앞에 있는 시작점에서 만나게 되기 때문에 앞에 있는 시작점을 리턴해 주면 되고요.

방향이 반대 방향이라면 서로가 마주 보고 있는지 -> <- 아니면 <- -> 서로 다른 방향으로 진행하는지에 따라서 교점이 존재 하거나 존재하지 않게 됩니다.

마주보는 방향을 (l.y1 - r.y1 ) * l.dy < 0 으로 판단을 했는데요.

l 선분이 (0,2) -> (0,1) 로 진행을 하고 있고 r 선분은 (0.0) -> (0,1) 로 진행을 하는 선분이라고 가정을 해 보면

l.dy 는 음수값이 나오는데 l.y1 이 r.y1 보다 큰 경우이기 때문에 마주보고 있다는 것을 알 수 있겠죠.^^

수직선이 아닌 경우는 x축을 가지고 동일하게 처리해 주면 됩니다.

위의 예제는 평행이 아니므로 직선에서는 반드시 교점이 존재하게 되는데요.

이렇게 교점이 나온 경우 반직선이므로 해당 영역 내에서 만나는 부분이 있는지를 판단 해 주어야 합니다.

예를 들면 (1,1) -> (2,2) 방향으로 진행하는 직선과 (0,0) -> (1,0) 의 방향으로 진행하는 직선은 교점이(0,0) 이 나오지만 실제로는 만나지 않는데 이러한 부분을 걸러 내 주면 되는데요.

l 선분이 수직선일때 r선분이 수직선일때 아닐때 판단하는 루틴이예요.

위의 예처럼 (1,1)->(2,2) 와 (0,0) ->(1,0) 과 같은 경우

(2,2)->(3,3) 와 (2,0) -> (1,1) 과 같은 선분을 걸러 내는 경우를 생각해 보시면 위의 

    if(isVertical(l) && ( (y-l.y1) * l.dy <0)) return Point(); 

    if(isVertical(r) && ( (y-r.y1) * r.dy < 0) )return Point();

    if(!isVertical(l) && ((x-l.x1)*l.dx < 0)) return Point();

    if(!isVertical(r) && ((x-r.x1)*r.dx < 0)) return Point();

이 부분의 의미를 아실 거예요.

 

이렇게 함수를 만들었다면

마지막으로 메인에서 교점의 갯수를 세 주시면 되는데...

메인 부분은 다음과 같이 간단하게 처리 할 수가 있습니다.

 

    cin >> N >> L; 

    for(int i=0;i<N;i++)

    {

        int x1,y1,x2,y2;

        cin >> x1 >> y1 >> x2 >> y2;

        line[i].init(x1,y1,x2,y2);

    }

 

    for(int i=0;i<N;i++)

    {

        for(int j=i+1;j<N;j++)

        {

            Point pt;

            pt = LineIntersection(line[i],line[j]);

            if(pt.p) cnt++;

        }

    }

    cout << cnt;

 

 

기하알고리즘이란? https://wondangcom.com/453?category=717978

두선분의 교점 찾기 https://wondangcom.com/466

반직선의 교점찾기1 https://wondangcom.com/903

반직선의 교점찾기2 https://wondangcom.com/930

 

 

  • 휴식같은 친구 2019.07.12 10:56 신고    

    알고리즘 구현 정말 어렵네요.ㅎㅎ
    수학시간에 직전의 방정식에서 교점찾기하는거 배운거 기억나는데 훨 어려워보여요.ㅎㅎ

  • 라미드니오니 2019.07.12 12:29 신고    

    아이고, 잘못했습니다.ㅠ

  • 유하v 2019.07.12 16:55 신고    

    무슨 얘기인지 1도 못알아듣겠지만 공부하는 학생들에게 좋은 정보가 되길 바랍니다 ㅎ

  • 행복사냥이 2019.07.12 19:40 신고    

    ㅎ 모르겠지만 좋은 내용입니다. ^^

  • 버블프라이스 2019.07.13 03:56 신고    

    아... 정말 어렵네요;;
    반직선의 교점찾기 알고리즘 구현은 잘 이해가 안가지만 공감 누르고 갑니다 ^^; 좋은 주말 보내시길 바래요

  • 청결원 2019.07.13 06:39 신고    

    포스팅 잘 보고 갑니다~
    즐거운 주말 보내세요~

  • 핑구야 날자 2019.07.13 07:08    

    문제를 자꾸 그러다 보면 실력 보는 거 재미도 있을 것 같아요

  • 공수래공수거 2019.07.13 09:15 신고    

    전 어렵지만 도움되시는분 분명 계실듯 합니다..ㅎ
    즐거운 주말 보내시기 바랍니다.^^

  • 잉여토기 2019.07.14 12:51 신고    

    반직선의 교점을 찾는 함수 구현법이군요.
    관련 분야 공부하시는 분들께 많은 도움이 될 듯해요.

  • 드래곤포토 2019.07.14 16:22 신고    

    좋은하루되세요 ^^

  • 핑구야날자 2019.07.15 06:38    

    문제가 쉽지는 않지만 풀면서 실력이 늘겠는데요