algospot.com :: 과거 게시판: [editorial] RUN Programming Contest

[editorial] RUN Programming Contest - C. 로미엣과 줄리오

Taeyoon_Lee
안녕하세요.
로미엣과 줄리오 문제 출제자입니다.
출제 과정과 해설, 그리고 뒷이야기 등을 써보겠습니다.
이 문제는 회사에서 3D 공부를 하다가 bounding-box에서 영감(?)을 얻어서 출제하게 되었습니다.
문제 자체는 어렵지 않게 만들었는데, 이야기를 짓는 게 상당히 어려웠어요.
게다가 입출력을 만드는 일은 정말 거의 5일 정도 걸린 것 같네요. ( ..)
다음부터는 기하 문제는 좀 더 신중하게 만들어야 할 것 같습니다...
해법입니다.
우선 기본적으로 점과 선분 사이의 최단 거리를 구하는 방법을 알아야 합니다.
여러가지 방법이 있을 텐데, 제가 애용하는 방법은 선분을 밑변으로 하는 삼각형을 만드는 것입니다.
삼각형을 만들면 아래와 같이 두가지 경우가 생깁니다.

1. 둔각삼각형이 되는 경우
이런 경우에는 선분의 두 끝점과 점 사이 거리를 구하면,
더 가까운 거리가 점과 선분 사이의 최단 거리가 됩니다.

2. 예각삼각형이 되는 경우
이 경우에는 이 삼각형의 넓이를 구한 후에,
넓이x2 / 밑변 을 구하면 그게 점과 선분 사이의 최단 거리가 됩니다.
밑변 곱하기 높이 나누기 2 가 삼각형의 넓이니까요. (중학교 수학이죠''?)
점과 선분 사이의 최단 거리를 구할 수 있다면, 섬과 섬 사이의 최단 거리도 구할 수 있습니다.
섬 A와 섬 B가 있다고 할 때, 두 섬 A, B 사이의 최단 거리는
"섬 A와 섬 B에 속하는 모든 선분 쌍 사이의 최단 거리"라고 정의할 수 있습니다.
선분과 선분 사이의 최단 거리는 선분과 점 사이의 거리를 4번 계산하면 구할 수 있습니다.
아래 그림을 예로 들면,

min( AB와 C 사이의 거리, AB와 D 사이의 거리, CD와 A 사이의 거리, CD와 B 사이의 거리 )
가 됩니다. 그림의 경우에는 AB와 C 사이의 거리를 구했을 때, 최단 거리를 얻을 수 있겠죠.
다시 "섬 A와 섬 B에 속하는 모든 선분 쌍 사이의 최단 거리"라는 말을 곰곰이 생각해보면,
굳이 모든 선분과 선분 쌍 사이의 최단 거리를 구할 필요는 없어 보입니다.
아래와 같이 구하면 계산량을 줄일 수 있겠지요.
min( 섬 A의 모든 점과 섬 B의 모든 선분 쌍 사이의 최단 거리, 섬 A의 모든 선분과 섬 B의 모든 점 쌍 사이의 최단거리 )
음.. 말이 길어서 잘 이해가 안 되시면, 코드를 보는 것을 추천합니다. ( ..)
이런 기본적인 방법으로 모든 두 섬 사이의 최단 거리를 구하면,
시간복잡도는 O( n^2 * m^2 ) 이 됩니다. ( n은 섬의 개수, m은 섬의 최대 꼭지점 수. )
정수 계산이라면 충분히 시간 안에 나올만 하지만, 실수 계산이기 때문에
이런 시간복잡도로는 시간 제한에 걸리게 됩니다. (아슬아슬하게 통과하신 분도 있는 것 같습니다만..)
시간 제한에 걸리지 않기 위해서는 알고리즘의 개선이 필요합니다.
우선 제가 사용한 아주 간단한 개선 방법은 섬이 볼록다각형이라는 것을 이용하는 것입니다.
1. 각 섬의 가장 왼쪽 점, 오른쪽 점, 아래 점, 위 점을 찾아서 섬을 포함하는 직사각형을 구합니다.
2. 모든 섬 쌍 사이 최단 거리를 구합니다.
3. 지금 구하려는 두 섬의 직사각형 사이 거리가 현재 구한 답보다 크다면, 이 두 섬 사이의 거리는 계산하지 않고 넘어갑니다.
이 방법을 이용하면 계산량이 신기하게도(?) 매우 줄어듭니다.
절대 답이 될 수 없는 쌍을 골라내면서 계산을 진행하기 때문에 O( n^2 ) 이던 계산량이
expected O( log(n^2) ) 으로 줄어들게 되죠. 물론 최악의 경우에는 n^2에 가까운 계산이 필요할 수도 있지만
한번 랜덤하게 섞어주거나 하면, 퀵소트처럼(?) 최악에 빠질 확률이 매우 줄어듭니다.
지금까지 쓴 해법을 코드로 옮기면 아래와 같습니다.
```
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define FOR(i,a,b) for( int i=(a); i<(b); ++i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define ERR 1e-9
#define SQ(a) ((a)*(a))
#define SQDS(a,b) ( SQ( (a).x-(b).x )+ SQ( (a).y-(b).y )) 
#define ABS(a) (((a)<0) ? -(a) : (a))
struct pnt {
    double x,y;
};
double segdis(pnt sa,pnt sb,pnt pa) //선분과 점 사이의 거리
{
    double a,b,c,t;
    a=SQDS(sa,pa);
    b=SQDS(sb,pa);
    c=SQDS(sa,sb);
    if (a<b) swap(a,b);
    if (a>b+c || c<ERR) return sqrt(b); // 둔각이라면
    t=sa.x*sb.y-sb.x*sa.y+sb.x*pa.y-pa.x*sb.y+pa.x*sa.y-sa.x*pa.y;
    return ABS(t)/sqrt(c); // 예각이라면
}
int n,m[128];
pnt dt[128][32];
pnt rt[128][8];
double findmin(pnt *a,pnt *b,int la,int lb)
{
    double mn=1e100;
    REP(i,la) REP(j,lb) {
        mn=min(mn,segdis(a[i],a[i+1],b[j]));
        mn=min(mn,segdis(b[j],b[j+1],a[i]));
    }
    return mn;
}
int main()
{
    int tn;
    scanf("%d",&tn);
    while (tn--) {
        scanf("%d",&n);
        REP(i,n) {
            cin>>m[i];
            REP(j,m[i])
                scanf("%lf%lf",&dt[i][j].x,&dt[i][j].y);
            dt[i][m[i]]=dt[i][0];
        }
        double l,r,t,b;
        REP(i,n) {
            l=r=dt[i][0].x;
            t=b=dt[i][0].y;
            FOR(j,1,m[i]) {
                l=min(l,dt[i][j].x);
                r=max(r,dt[i][j].x);
                t=max(t,dt[i][j].y);
                b=min(b,dt[i][j].y);
            }
            rt[i][0].x=rt[i][1].x=l;
            rt[i][2].x=rt[i][3].x=r;
            rt[i][0].y=rt[i][3].y=t;
            rt[i][1].y=rt[i][2].y=b;
            rt[i][4]=rt[i][0];
        }
        double dp=1e100,dis;
        int pa,pb;
        REP(i,n) FOR(j,i+1,n) 
            if (dp+ERR > findmin(rt[i],rt[j],4,4))
            {
                dis=findmin(dt[i],dt[j],m[i],m[j]);
                if (dp>dis) {
                    dp=dis;
                    pa=i,pb=j;
                }
            }
        printf("%d %dn",pa+1,pb+1);
        printf("%.2lfn",dp);
    }
    return 0;
}
```
이 문제는 56개의 답안 중에 8개만 통과하는 꽤 저조한 성공률을 보였습니다.
가장 빠른 Yes는 team14 도경이형이 78분에 받았네요. 역시..+_+)=b
음.. 조금 뒷이야기를 하자면.. 출제자로서는 무엇보다도 입력을 만드는 게 어려웠습니다..
처음에는 최대 30각형 정도로 하는 게 좋지 않을까 생각했는데,
볼록다각형 만드는 일이 생각보다 엄청 어렵더군요..
우선 가장 쉽게는 어떤 직사각형 범위 안에 랜덤하게 점을 생성하면서
컨벡스홀을 씌우는 방법을 생각할 수 있는데, 이렇게 하면 99.99% 확률로
그 범위에 딱 들어맞는 사각형에 가까운 도형이 만들어지더군요..OTL
30각형이면 각 꼭지점에서의 각도가 평균 168도가 됩니다.
거의 직선에 가깝죠.. '';; 이래선 아무래도 안되겠다 싶어서
20각형으로 제한을 줄이고, 다시 방법을 궁리한 끝에...
우선 대충 10각형 정도의 도형을 만들고, 각 선분 사이에
선분을 약간 벗어나는 점을 찍은 다음에 다시 컨벡스홀을 씌워서
도형을 만들었어요. 그제서야 좀 여러가지 모양의 다각형이 나오더군요.
음.. 그리고 데이터를 만들면서 입력 데이터에 오류가 없을지 걱정돼서
데이터를 그림으로 바꿔주는 툴까지 만들었어요...

데이터만 거의 5일동안 만든 것 같네요...ㅠㅠ 다시는 기하문제는
출제하고 싶지 않아요.. 하지만 제가 출제를 해서 대회를 해본 것도 처음이고,
가장 많이 공들인 문제라 애착은 제일 많이 가네요. >,<
이것으로 에디토리얼을 마치겠습니다.

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

15년 전

9개의 댓글이 있습니다.

walsub

에디토리얼 멋지네요! ㅋㅋ 수고하셨습니다 ㅎ

15년 전 link
Toivoa

역시 유사문제로는 UVA에 River Crossing (http://acm.uva.es/p/v105/10514.html) 이 있습니다.

15년 전 link
고글

형은 문제가 나오면 ㅋㅋ uva의 유사문제를 바로바로 알려주는군요..ㅋ

15년 전 link
Toivoa

내가 본게 몇갠데 'ㅅ'

15년 전 link
VOCList

n[..]

15년 전 link
Taeyoon_Lee

역시 이 문제를 만들기 위해 참고한 문제입니다. ㅠㅠ

15년 전 link
@,.@

두 convex hull의 최소거리는 convex hull이 구해져 있으면 O(m)에 구할수 있습니다. Rotating Calipers라고 재미있는 주제로 연구 되었습니다(알고리즘을 보시려면 http://cgm.cs.mcgill.ca/~orm/rotcal.html, 증명도 같이 보시려면 논문 Godfried Toussaint, Solving Geometric Problems with the Rotating Calipers).
그리고 한가지 궁금한점은 이때까지 구한 최소거리와 다음 두 convex hull의 bounding box의 거리를 비교하면 계산량이 expected O( log(n^2) ) 되는게 맞는건가요?.
그럼 즐거운 하루 되세요..^^;
p.s 저도 어느새 레벨2가 되어 있군요..ㅋㅋ

14년 전 link
Taeyoon_Lee

일단 제가 만든 데이터에서는 거의 그랬어요.. n이 100인 경우, 그림같이 랜덤(?)하게 섬이 분포되어 있으면 실제로 계산 해보는 섬 쌍은 15개 내외더라구요.
두 섬을 짝짓는 대략 n^2 가지 경우의 각각의 거리가 오름차순으로 D[1], D[2], D[3], ... , D[n^2] 라고 할 때, (답은 D[1]이 되겠죠)
랜덤하게 두 쌍을 고르면 D[k]가 전부 같은 확률로 뽑힐 테니, 기대값이 D[n^2 / 2]은 되겠죠.
어떤 D[k]를 뽑았다고 치면, D[k+1], D[k+2] ... 등은 더이상 고려 대상에서 제외될 테니, expected O( log (n^2) ) 쯤 되지 않을까 싶네요.
다만 제가 생각한 최악의 경우는, 도형이 프렉탈처럼 연속되는 경우인데요,
그런 경우에는 프렉탈처럼 연속돼서 그려진 도형들의 bounding box가 전부 겹쳐지겠죠.
하지만 좌표가 정수로 치면 100만 이하이기 때문에 해봐야 20개 이상 겹치기 힘들 겁니다.
게다가 20각형을 프렉탈로 만들려고 하면... ( ..)
사실 조금.. 완벽한 해법이라고 하긴 어려운데요.. 'ㅁ'
처음부터 적당히 프루닝 해주면 통과하게끔 설계(?)를 했습니다.
그러니까... 결론은....
다 출제자가 무능한 탓입니다..ㅠㅠ

14년 전 link
@,.@

이해가 안되서 질문한겁니다..@,.@ 너무 자책하지 마세요..ㅡㅜ

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

walsub: 에디토리얼 멋지네요! ㅋㅋ 수고하셨습니다 ㅎ

15년 전 link

Toivoa: 역시 유사문제로는 UVA에 River Crossing (http://acm.uva.es/p/v105/10514.html) 이 있습니다.

15년 전 link

고글: 형은 문제가 나오면 ㅋㅋ uva의 유사문제를 바로바로 알려주는군요..ㅋ

15년 전 link

Toivoa: 내가 본게 몇갠데 'ㅅ'

15년 전 link

VOCList: n[..]

15년 전 link

Taeyoon_Lee: 역시 이 문제를 만들기 위해 참고한 문제입니다. ㅠㅠ

15년 전 link

@,.@: 두 convex hull의 최소거리는 convex hull이 구해져 있으면 O(m)에 구할수 있습니다. Rotating Calipers라고 재미있는 주제로 연구 되었습니다(알고리즘을 보시려면 http://cgm.cs.mcgill.ca/~orm/rotcal.html, 증명도 같이 보시려면 논문 Godfried Toussaint, Solving Geometric Problems with the Rotating Calipers).
그리고 한가지 궁금한점은 이때까지 구한 최소거리와 다음 두 convex hull의 bounding box의 거리를 비교하면 계산량이 expected O( log(n^2) ) 되는게 맞는건가요?.
그럼 즐거운 하루 되세요..^^;
p.s 저도 어느새 레벨2가 되어 있군요..ㅋㅋ

14년 전 link

Taeyoon_Lee: 일단 제가 만든 데이터에서는 거의 그랬어요.. n이 100인 경우, 그림같이 랜덤(?)하게 섬이 분포되어 있으면 실제로 계산 해보는 섬 쌍은 15개 내외더라구요.
두 섬을 짝짓는 대략 n^2 가지 경우의 각각의 거리가 오름차순으로 D[1], D[2], D[3], ... , D[n^2] 라고 할 때, (답은 D[1]이 되겠죠)
랜덤하게 두 쌍을 고르면 D[k]가 전부 같은 확률로 뽑힐 테니, 기대값이 D[n^2 / 2]은 되겠죠.
어떤 D[k]를 뽑았다고 치면, D[k+1], D[k+2] ... 등은 더이상 고려 대상에서 제외될 테니, expected O( log (n^2) ) 쯤 되지 않을까 싶네요.
다만 제가 생각한 최악의 경우는, 도형이 프렉탈처럼 연속되는 경우인데요,
그런 경우에는 프렉탈처럼 연속돼서 그려진 도형들의 bounding box가 전부 겹쳐지겠죠.
하지만 좌표가 정수로 치면 100만 이하이기 때문에 해봐야 20개 이상 겹치기 힘들 겁니다.
게다가 20각형을 프렉탈로 만들려고 하면... ( ..)
사실 조금.. 완벽한 해법이라고 하긴 어려운데요.. 'ㅁ'
처음부터 적당히 프루닝 해주면 통과하게끔 설계(?)를 했습니다.
그러니까... 결론은....
다 출제자가 무능한 탓입니다..ㅠㅠ

14년 전 link

@,.@: 이해가 안되서 질문한겁니다..@,.@ 너무 자책하지 마세요..ㅡㅜ

14년 전 link

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

SINCE 2007

다가오는 이벤트들

[editorial] RUN Programming Contest - C. 로미엣과 줄리오

9개의 댓글이 있습니다.