idea - 원에서 두 호의 위치 관계

문제를 풀다가 문제에서 쓰이는 구현의 좋은 아이디어가 떠올라서 글을 쓰려고 한다. 엄청나게 대단한 것은 아니지만, 이 아이디어를 쓰지 않고 구현을 하면 구현을 포기할 정도로 역겨워지며, 꼭 기억하고 싶기 때문에 글로 남기려고 한다.

원에 호가 두 개 있다. 그 두 개의 호에 대한 위치관계를 알아내는 것이 목표이다. 원에 n개의 지점이 있고, 두 개의 지점 번호를 통해서 호를 표기한다. (a,b)에서 b<a면 n을 넘어가는 형태의 호이다. 이 때문에 처리해야할 예외와 경우가 너무 많이 나오게 된다. 

검은색 호를 기준으로 나머지 호 들을 5가지 관계로 분류할 수 있다. 
1. 빨간색 : 검은 색 구간을 포함하는 호
2. 주황색 : 겹치지 않는 호
3. 노란색 : 검은 색의 왼쪽 부분이 겹치는 호
4. 초록색 : 검은 색의 오른쪽 부분이 겹치는 호
5. 파란색 : 구간 안에 포함되어 있는 호.
6. 투명색 : 검은 색의 왼쪽 부분과 오른쪽 부분이 모두 겹치는 호

 두 개의 호를 a,b. 왼쪽값과 오른쪽 값을 a.ff,a.ss 와 같이 표기하자. 아이디어는 a.ff 를 0으로 두고 새로 원을 설정해서 푸는 것이다. 즉, a.ff,a.ss,b.ff,b.ss 4가지 값 모두에 a.ff를 빼서 상대적 값으로 다시 설정한 후에 경우를 나누면 간단하게 해결할 수 있다. 왼쪽 값을 포함하고 있으면 b.ff>b.ss가 되며, 나머지는 보이는 그대로 대소 관계에 따라서 경우가 나온다. 

코드는 아래와 같이 나온다.

ll mat(pii a,pii b){
    ll p=a.ff;
    a.ff=(a.ff+nn-p)%nn;
    a.ss=(a.ss+nn-p)%nn;
    b.ff=(b.ff+nn-p)%nn;
    b.ss=(b.ss+nn-p)%nn;
    //printf("%lld %lld %lld %lld\n",a.ff,a.ss,b.ff,b.ss);
    if(b.ff==0){
        if(b.ss<a.ss) return 0;
        else return 3;
    }
    if(b.ff>b.ss){
        if(b.ff<=a.ss) return 4;
        if(a.ss<=b.ss) return 3;
        else return 1;
    }
    if(a.ss<b.ff) return -1;
    if(b.ss<=a.ss) return 0;
    return 2;
}