2010년 인터넷 예선 sewege ..

  • Sejoure
    Sejoure

    기하 문제인데요.
    대략적인 문제 설명은
    임의의 점들이 N개 뿌려져 있을때
    그 사이(도시 직사각형 범위 안에서.. 도시직사각형은 점을 모두 포함합니다)에 직선을 하나 그어
    그 직선과 가장가까운 점의 거리가(각 점에서 직선으로의 수선을 내린 거리 중 최단거리)
    가장 멀게 하게끔 직선을 긋는 것이 문제입니다.(그 거리를 구하는 것임)

    몇 시간의 장고 끝에..
    1. 도시 직사각형의 직선이 답이 되거나 직사각형의 꼭지점을 지나는 직선이 답이 될 가능성이 있다.
    2. 두점 사이의 거리 중 절반이 답이 된다, 단, 두 점 사이의 거리를 결정하는 선분에 수직하는 직선을 각 점에서 그었을때 그 사이에 점이 포함되어선 안된다.
    3. 모든 두점에 대하여 직선을 그었을 때 그 직선에 따라 좌표정렬을 했을 때 바로 옆에있는 양 쪽 점 두 개중 먼거리에 있는 것을 취해 그것의 절반이 답이 될 가능성이 있다.

    1,2,3에서 구한 길이 중에 가장 긴것이 답이 될 거라고.. 생각이 드는군요 확실치 않지만.
    2, 3을 구하기 위해서 얼핏생각하면, N^3방법 밖에 떠오르지 않았는데요 .
    일단 y좌표대로 정렬한후, 모든 두점에 대하여 직선을 그었을 때 기울기 순서대로 정렬하여 그 두점을 체크해 나가면 두점이 체크될때 그 두 점의 좌표 순서만 바꾸면 정렬 상태가 유지되는 것 같더라구요.(정렬 상태가 유지되면 두점을 직선으로 그었을 때 바로 옆 두 점을 알수 있으니) 이래서 N^2logN만에 될수도 있다는 생각은 했습니다만..

    하지만, 코딩할 엄두가 안나기도 하고..
    위 가정이 맞기는 맞는건가요 ㅠ.ㅠ 도와주세요.

    그리고, 인터넷 찾다보니 보로노이 다이어그램인가.. 그런게 있다던데
    그걸 이용하는 건가요 ?
    간단하게 구현방법이나, 아니면 잘 설명되어있는 곳 링크라도 걸어주시면 감사하겠습니다.
    아니면 이 문제 채점할수있는 곳이라도 알려주시면 감사하겠습니다 ㅠ 못찾겠어요 ㅠ


    8년 전
4개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    안녕하세요.
    Sejoure님의 방법을 다 이해하지 못해서 그런데 (0,0) (10,0) (5,10)의 경우엔 y=5로 한가운데를 가로지르는 직선이 답일거같은데 위 3가지 경우에 포함되나요?

    저도 짜본적은 없지만 대략적으로 생각한 풀이는 가능한 거리 d를 이용한 바이너리 서치로 풀수있지 않을까하는 방법입니다. 모든 점을 기준으로 반지름이 d인 원을 그려서 어떤 원에도 터치되지않는 직선을 그릴수 있다면 더 큰 거리에 도전해 볼 수 있습니다.

    그러면 어떤 원에도 터치되지 않는 직선을 어떻게 찾느냐가 문제가 되는데, 저는 이 직선이 최소한 두 개의 원에 접하거나 혹은 직사각형의 테두리상에 존재한다고 생각합니다. 두 개의 원에 접하는 직선의 공식은 쉽게 유도할수 있고 이 직선이 다른 원을 안 건드리는지 체크해보는게 코딩은 쉽지만 O(N^3)의 시간이 걸리더군요.

    한 원에서 다른 원으로 그어서 생기는 4개의 접선을 그리고 고민해보시면(...) 각 접점의 사이를 지나는 접선을 그려서는 그 원에 충돌해 버린다는 것을 알 수 있습니다. 다시 말해 임의의 원은 다른 원에게 접점을 만들수 없는 금지영역(?)을 만들수 있습니다. 그렇다면 우리가 할일은 각 원에 모든 원을 투영해보고 금지영역이 모든 원을 덮었는지 안덮었는지 체크해보는 것입니다. 이 방법은 매우 귀찮지만-_- 각 원당 O(N lg N)시간에 할수 있기 때문에 전체원에 대한 검사를 O(N^2 lg N)번에 할수 있습니다. 바이너리 서치상수를 적당히 잡아서 돌려주시면 아마 답은 나올거같네요.

    보로노이 다이어그램은 대회중에 구현하기에는 상당히 복잡해서 반드시 보로노이로만! 구현가능한 문제는 안나올거같습니다..아마..


    8년 전 link
  • Sejoure
    Sejoure

    Parametric Search를 이용하신다는 뜻이군요. 하지만 코딩이 좀 안드로메다로 가지 않을까요 ㅠㅠ 사실 접선으로 금지구역을 설정한다 하더라도 각 접선이 그 금지구역에 해당하는지 체크하는 것도 쉽지 않을 것 같습니다.

    Kureyo님이 말씀하신 예제는 제가 말씀드린 3번 방법으로 해결가능합니다. (0,0) (10,0) 이 하나의 직선을 이루고, (5,10)은 위에 그은 직선을 축으로 해서 정렬 했을 때 바로 옆에 있는 점이므로 직선과 점 사이의 거리 10을 반으로나눈 5를 출력하게 됩니다.

    제 생각에 가정은 맞는 거 같은데요. (사실 점 3개가 모였을 때 둔각 삼각형을 이룬다면 2번 조건이 되고, 예각 삼각형이면 3번조건이 됩니다. 점 4개 이상일때는 점 3개이하만이 거리에 관여하고 나머지 항상 무시한 모양이 되죠. 이 가정이 맞다면 1,2,3번으로 해결되는 것 같습니다.)

    위의 3번 방법을 짜려면 N^2으로 한 직선을 정하고, 그 직선을 임의의 y'축으로 보았을 때 수직인 축을 x'축이라 하면, 그 x'좌표가 증가하는 순서.. 뭔가 너무 어렵게 말씀드렸는데 어떤 직선을 정했을 때 거리순서로 뒀을 때 거리가 가장 짧은 두점, 즉, x'좌표대로 했을 때 바로 옆의 두점을 구하는 것이 N번 소요되므로 N^3인데 N=1000이니 조금 어렵지 않나 싶습니다.

    그래서 좌표 정렬이 위에 본문에 설명한 저런식으로 가능할지 의문입니다. 모든 점의 쌍을 이은 직선을 기울기 순서대로 정렬한후 그 기울기 순서대로 점의 쌍을 체크하여 그 기울기가 넘어가면 점의 순서를 바꾸는 방법으로 정렬 상태가 유지 되는지 궁금합니다. 예제 몇개만 넣어서는 되는 것 같지만 왠지 반례가 있을 듯한 불안감이 드는군요 ㅠ.ㅠ


    8년 전 link
  • Dynamical
    Dynamical

    먼저 직선이 convex hull의 안쪽에 위치한다는 가정하에서.. (일단 바깥쪽에 위치한 경우는 따로 처리하기 쉬우므로)
    일단 optimal solution의 기울기는 항상
    1. 어떤 두 점을 잇는 선과 수직하거나
    2. 어떤 두 점을 잇는 선과 평행하거나
    로 만들어줄 수 있고, 따라서 약 n^2개의 기울기 후보군이 있으니, 이 기울기 대로 정렬을 해서 순서대로 회전을 해 보면, 그 기울기에 따른 '정렬 순서'가 일단 나름 연속적으로 바뀌는 것을 이용하면 n^2 log n에 할 수 있습니다. 다만 한 직선 위에 3개의 점이 올려질 수 있으므로, 이 연속적으로 바뀌는 것을 다루기에 좀 조잡해 보이네요.

    이 문제는 Widest-Corridor Problem으로 불리는데, Duality를 이용하면 n^2까지 떨어졌던 걸로 알고 있습니다. 구글링 하면 이에 관한 논문을 금방 찾으실 수 있을듯..


    8년 전 link
  • Sejoure
    Sejoure

    답글 감사합니다. 당장 검색해보아야 겠군요.


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