| [ QuizWit ] in KIDS 글 쓴 이(By): perdu (.) 날 짜 (Date): 1997년10월01일(수) 03시54분01초 ROK 제 목(Title): Re: 그때 그 숲 - 더 작은 값이... [또 씁니다.] Pick's theorem을 고려할 때, 주어진 문제를 해결하기 위한 답은, 삼각형 아니면 사각형이고 경계선에 걸리는 나무의 수가 4개여야 하는군요. 삼각형의 경우, 정삼각형을 이용한대도 둘레의 lower bound가 3*sqrt(230.???) > 45 이군요. 따라서 사각형을 이용해야 최소 둘레를 구할 수 있겠네요. 이때는 꼭지점을 제외한 모든 경계선에 나무가 걸리면 아웃이므로, 각 경계선 벡터를 (x,y)로 놓았을 때, x와 y는 서로 소 관계에 있어야 하겠네요. (천리안 아저씨가 내놓은 답은 6과 8이 서로 소가 아니었죠) 또한 각 벡터의 길이의 제곱은 100에 가까와야 하고요. 적어도 한 벡터의 길이는 10보다 작아야 합니다. (그렇지 않으면 면적이 100보다 커지게 되는 수가 생김.) 정사각형에 가깝게 되기 위해서는 잇닿은 벡터의 내적이 0에 가까와야 하는데, 이를 위해선 벡터 (x,y)와 잇닿은 벡터가 (y,-x) 혹은 (-y,x)와 가까와야 되겠군요. 이와 같은 조건들을 만족하는 (x,y) pair들을 찾으면 답을 구할 수 있겠지요. -- l'ange perdu |