4개의 댓글이 있습니다.
-
-
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)번에 할수 있습니다. 바이너리 서치상수를 적당히 잡아서 돌려주시면 아마 답은 나올거같네요.
보로노이 다이어그램은 대회중에 구현하기에는 상당히 복잡해서 반드시 보로노이로만! 구현가능한 문제는 안나올거같습니다..아마..
12년 전 link
-
-
-
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이니 조금 어렵지 않나 싶습니다.
그래서 좌표 정렬이 위에 본문에 설명한 저런식으로 가능할지 의문입니다. 모든 점의 쌍을 이은 직선을 기울기 순서대로 정렬한후 그 기울기 순서대로 점의 쌍을 체크하여 그 기울기가 넘어가면 점의 순서를 바꾸는 방법으로 정렬 상태가 유지 되는지 궁금합니다. 예제 몇개만 넣어서는 되는 것 같지만 왠지 반례가 있을 듯한 불안감이 드는군요 ㅠ.ㅠ
12년 전 link
-
-
-
Dynamical -
먼저 직선이 convex hull의 안쪽에 위치한다는 가정하에서.. (일단 바깥쪽에 위치한 경우는 따로 처리하기 쉬우므로)
일단 optimal solution의 기울기는 항상
1. 어떤 두 점을 잇는 선과 수직하거나
2. 어떤 두 점을 잇는 선과 평행하거나
로 만들어줄 수 있고, 따라서 약 n^2개의 기울기 후보군이 있으니, 이 기울기 대로 정렬을 해서 순서대로 회전을 해 보면, 그 기울기에 따른 '정렬 순서'가 일단 나름 연속적으로 바뀌는 것을 이용하면 n^2 log n에 할 수 있습니다. 다만 한 직선 위에 3개의 점이 올려질 수 있으므로, 이 연속적으로 바뀌는 것을 다루기에 좀 조잡해 보이네요.이 문제는 Widest-Corridor Problem으로 불리는데, Duality를 이용하면 n^2까지 떨어졌던 걸로 알고 있습니다. 구글링 하면 이에 관한 논문을 금방 찾으실 수 있을듯..
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Sejoure
기하 문제인데요.
대략적인 문제 설명은
임의의 점들이 N개 뿌려져 있을때
그 사이(도시 직사각형 범위 안에서.. 도시직사각형은 점을 모두 포함합니다)에 직선을 하나 그어
그 직선과 가장가까운 점의 거리가(각 점에서 직선으로의 수선을 내린 거리 중 최단거리)
가장 멀게 하게끔 직선을 긋는 것이 문제입니다.(그 거리를 구하는 것임)
몇 시간의 장고 끝에..
1. 도시 직사각형의 직선이 답이 되거나 직사각형의 꼭지점을 지나는 직선이 답이 될 가능성이 있다.
2. 두점 사이의 거리 중 절반이 답이 된다, 단, 두 점 사이의 거리를 결정하는 선분에 수직하는 직선을 각 점에서 그었을때 그 사이에 점이 포함되어선 안된다.
3. 모든 두점에 대하여 직선을 그었을 때 그 직선에 따라 좌표정렬을 했을 때 바로 옆에있는 양 쪽 점 두 개중 먼거리에 있는 것을 취해 그것의 절반이 답이 될 가능성이 있다.
1,2,3에서 구한 길이 중에 가장 긴것이 답이 될 거라고.. 생각이 드는군요 확실치 않지만.
2, 3을 구하기 위해서 얼핏생각하면, N^3방법 밖에 떠오르지 않았는데요 .
일단 y좌표대로 정렬한후, 모든 두점에 대하여 직선을 그었을 때 기울기 순서대로 정렬하여 그 두점을 체크해 나가면 두점이 체크될때 그 두 점의 좌표 순서만 바꾸면 정렬 상태가 유지되는 것 같더라구요.(정렬 상태가 유지되면 두점을 직선으로 그었을 때 바로 옆 두 점을 알수 있으니) 이래서 N^2logN만에 될수도 있다는 생각은 했습니다만..
하지만, 코딩할 엄두가 안나기도 하고..
위 가정이 맞기는 맞는건가요 ㅠ.ㅠ 도와주세요.
그리고, 인터넷 찾다보니 보로노이 다이어그램인가.. 그런게 있다던데
그걸 이용하는 건가요 ?
간단하게 구현방법이나, 아니면 잘 설명되어있는 곳 링크라도 걸어주시면 감사하겠습니다.
아니면 이 문제 채점할수있는 곳이라도 알려주시면 감사하겠습니다 ㅠ 못찾겠어요 ㅠ
12년 전