[도전 28일차] 기하 구현 끝판왕, 달팽이

백준 6990 달팽이

 

2020/04/09 - [Problem Solving/KOI 고등부] - (※재도전 시급) [도전 11일차] 백준 6990 달팽이

4월 9일에 포기했던 문제를 6개월만에 다시 잡다.

6개월 전 시청한 IOI Korea님의 풀이와 나의 오랜 thinking이 합쳐져 구현에 온전히 집중할 수 있었다.

문제 : 백준 6990 달팽이

문제 링크

 

문제 요약 : 

 

 

L * L 크기의 좌표 평면에 N 마리 달팽이가 있다.

달팽이들의 시작 위치는 정해져 있고 일직선으로 움직인다.

달팽이들은 1초에 1의 속도로 움직인다. 달팽이는 다른 달팽이가 움직인 흔적이나 벽에 부딪혔을 때 멈춘다. 달팽이들의 시작 위치와 초기 방향이 주어졌을 때 모든 달팽이들이 멈추는데까지 걸리는 시간은 얼마일까? 모든 달팽이들은 (0,0) , (L,L)을 왼쪽 아래, 오른쪽 위 끝점으로 하는 정사각형 안에서 이동을 시작하므로 언젠가 멈추게 되어 있다.

 

 

풀이 : 

 

사용 알고리즘 : 정렬, 기하

  

달팽이는 하나의 반직선에 대응이 된다. 4개의 벽도 각각 선분에 대응된다.

편의 상 반직선을 선분으로 만들자. 시작점과 기울기가 주어지면 끝점을 시작점에서 멀리 잡으면 된다.

 

두 선분이 만나는 상황을 하나의 이벤트로 생각해보자.

달팽이의 수 N<=1000 이므로 두 선분이 만나는 O(N^2)개의 이벤트들을 저장 가능하다.

 

이벤트를 나타내는 정보들은 다음과 같다.

이벤트 종류, 부딪히는 두 달팽이 A,B , 부딪히는 시간 t

 

#1 이벤트에는 세가지 종류가 있다.

type 0. 두 달팽이가 동시에 만난다.

type 1. 한 달팽이가 다른 달팽이의 흔적을 만난다.

type 2. 한 달팽이가 벽에 부딫힌다. (이때 B는 달팽이가 아니라 벽이다.)

 

#2 각 종류의 이벤트가 성립할 조건

type 0. A와 B가 동시에 만나야 한다. 그러기 위해서는 t 이전에 A와 B 모두 부딪힌 적이 없어야 한다. 이미 멈춘 달팽이와 충돌할 수는 없기 때문이다.

type 1. 먼저 A가 충돌한 적이 없어야 한다. 만약 B가 A가 충돌한 이후에 충돌한다면 B의 흔적이 남아있음은 자명하다. 그런데 B가 이 이벤트 전에 충돌한다면 B의 충돌은 이 이벤트에서 B가 그 교차점을 지나는 시점 이후에 이루어져야 한다. 만약 이 이벤트에서 A가 B의 흔적을 만나기 전에 B가 이미 멈춘 상태라면 B의 흔적은 존재할 수 없기 때문이다.

type 2. A가 충돌하지 않았다면 A는 벽과 충돌한다.

 

이벤트 간의 전후 관계가 매우 중요하다. 이에 우리는 각 이벤트들을 발생 시간에 따라 정렬하여 차례대로 처리한다. 그리고 마지막 유효한 이벤트의 발생 시간을 출력해주면 된다.

 

기하 알고리즘 구현에 익숙하지 않다면 강력하게 선분 교차 2 문제를 먼저 공부할 것을 권한다.

구현이 중요한 문제이기 때문에 전체 코드는 올리지 않지만, 기하 구현 코드를 올린다.

달팽이 문제는 스스로 풀 때 재미가 극대화되는 문제다.

 코드

typedef double C;
const C eps = 1e-7 , INF = 1e9;
typedef complex<C> P;
#define X real()
#define Y imag()
// P rotate(P p1,C degree){
//     return P*polar(1.0,degree);
// }
// C deg(P p1){
//     return arg(v);
// }
bool operator <(P p1,P p2){
    return abs(p1.X-p2.X)<eps?p1.Y<p2.Y:p1.X<p2.X;
}
C dist(P p1,P p2){
    return abs(p2-p1);
}
C cross(P p1,P p2){
    return (conj(p1)*p2).Y;
}
int ccw(P p1,P p2,P p3){
    C res = cross(p2-p1,p3-p2);
    if(abs(res)<eps) return 0; //colinear
    return res>0?1:-1;
 
}
 
struct line{
    P st,en;
    line(P a,P b):st(a),en(b){}
};
 
bool chkIntersect(line A,line B){
    P&a=A.st,&b=A.en,&c=B.st,&d=B.en;
    int ab = ccw(a,c,d) * ccw(b,c,d);
    int cd = ccw(c,a,b) * ccw(d,a,b);
    if(ab == 0 && cd == 0){
        if(b<a) swap(a,b);
        if(d<c) swap(c,d);
        return !(b<c||d<a);
    }
    return ab<=0 && cd<=0;
}
 
// 평행한 두 line의 교점을 res에 넣는다.
void parallelIntersect(line A,line B,P&res){
    //메인함수에서 체크하므로 겹치는게 보장된다.
    P&a=A.st,&b=A.en,&c=B.st,&d=B.en;
    if(a<b){
        if(c<d){
            if(c<a){
                res = a;
            }else{
                res = c;
            }
        }else{
            res = 0.5 * (a+c);
        }
    }else{
        if(c<d){
            res = 0.5 * (a+c);
        }else{
            if(c<a){
                res=c;
            }else{
                res=a;
            }
        }
    }
}
 
//직선의 교차점을 구해 res에 집어넣는다.
void lineIntersect(line A,line B,P&res){
    P&a=A.st,&b=A.en,&c=B.st,&d=B.en;
    int ab = ccw(a,c,d) * ccw(b,c,d);
    int cd = ccw(c,a,b) * ccw(d,a,b);
    if(ab == 0 && cd == 0){
        parallelIntersect(A,B,res);
        return;
    }
    b-=a; d-=c; 
    //a+pb = c+qd 
    C p = cross(c-a,d) / cross(b,d);
    res = a + p*b;
    return;
}
 
struct event{
    int type,s,e;
    //type 0 : 동시에 부딪힌다
    //type 1 : s가 e에 부딪힌다.
    //type 2 : s가 벽에 부딪힌다.
    double t1,t2;
    event(int p,int a,int b,double c,double d):type(p),s(a),e(b),t1(c),t2(d){}
    bool operator<(const event&tmp){
        return t1<tmp.t1;
    }
};

 

질문 환영합니다 :)

 

 

※오늘 문제부터 복습을 실시

UPD : Wednesday, October 14, 2020 2:53:40 AM GMT+09:00