6개의 댓글이 있습니다.

• 
  JongMan

  가장 먼 두 점이 convex hull 위에 있다는 거의 반례.. 는 아닌거 같고
  단조감소의 반례? 라고 생각해보니 꽤 트리비얼한 반례가 있는듯도.. 하네요 -_-;;; 얼레?

  
  17년 전 link

• 
  Kureyo

  어떻게 반례가 되는건가요 ?.?

  
  17년 전 link

• 
  JongMan

  아 제가 주장하고 있던 건, 어떤 점을 잡으면 다른 점까지의 거리들이 convex function 을 이룬다~ 따라서 터너리 서치로 풀 수 있다~ 라는 거였는데요.
  (-4,0) (4,0) (0,1) (0,-1) 를 네 점으로 갖는 마름모를 생각해 보면 (0,1) 입장에서 볼 때 가장 먼 점은 두 개 있죠.. 따라서 단조감소 주장은 사실이 아니고요.. 가장 먼 두 점 중의 하나를 잡았을때 다른 것 까지는 단조증가 + 단조감소 한다는 클레임으로 말을 바꿔야 할 것 같네요.
  이 경우 증명 가능할 것 같은데 글쎄요 음냐. 나중에. -_-;

  
  17년 전 link

• 
  JongMan

  AB=AC>BC 인 이등변삼각형 하나를 잡고.. 한 점 A 를 중심으로 하고 나머지 두 점 B, C 를 지나는 원을 상정합시다. 그리고 B, C 를 잇는 선분과 B, C 를 잇는 호 가 이루는 폐도형 안에 점을 하나 찍어서 ABDC 를 만들면 무조건 실패 !!
  OTL
  난 뭘 상정하고 풀었던거지? 제가 뭐 잘못했나요? -_-;

  
  17년 전 link

• 
  imyoyo

  극대값이 많이 나올 수 있는데 특별한 성질이 있는것 같지않네요.
  그나저나 이걸로 convex hull 구한 후 O(n)에 풀리네요~ rotating calipers

  
  17년 전 link

• 
  JongMan

  헉, rotating calipers! 이런게 있었지. 완젼 잊고 있었어용~ ^^;;

  
  17년 전 link

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