| [ QuizWit ] in KIDS 글 쓴 이(By): iLUSiON (BBiZi Land) 날 짜 (Date): 1998년 5월 15일 금요일 오전 09시 46분 29초 제 목(Title): [다른방법] 사각형 그리기 크크... 문제가 뭔지 다른사람들이 올린 포스팅 보고 알았습니다. 이방법은 어떤지요? 문제는 어떤점이 대각선방향으로 있는가 하는걸 찾는게 포인트인데 ( 님께서 reasonable한 입력이라고했으니까 오목사각형이 되는 케이스는 제외합니다. 오목사각형은 솔직히 사각형이라고 할수없습니다. 삼각형안에 점이 한개더있는 degenerate 한케이스라고 봐야겠지요. ) 이경우 a,b,c,d 가 이미 convex hull을 만든다고 가정할경우, 이중에서 두개의 점을 잇는 선분은 다른두점을 잇는 선분과 교차합니다. 서로 반대방향에 있다는거지요. ab, ac를 먼저 잡고 d가 ab,cd의 linear combination 으로 만들어지나 살핍니다. 즉 d= K_1 * ab + K_2 * ac 당연히 collinear case가 아닐경우 span(ab,ac) = R^2 입니다. 벡터스페이스의 베이스가 됩니다. 만약 K_1*K_2 > 0 일경우 (부호가 같을경우) 당연히 d는 대각선 방향에 있고 우리의 알고리듬은 terminate됩니다. 만약 K_1* K_2 < 0 이라면 d는 a 의 대각선 방향에 없다는소리지요. 어디있는지는 K_1, K_2 의 부호로 결정됩니다. ^^ 두개의 linear equation 을 품으로써 정확히 a,b,c,d의 relative 위치가 결정 됩니다. 크크..제방법보다 더쉬운방법은 없을것같군요. 흠..이걸 일반적인 polygon 콘스트럭션하는데 쓸수있을것같군요. 만약 그렇다면 제가 지금 기억이 가물가물한데 제가 학부때 convex hull만드는 알고리듬으로 stack이용해서 하는게 하나있는걸로 아는데 그게 제일빠른 알고리듬으로 알고있는데 음..알고리듬 이름이 뭐더라? (MIT 알고리듬교재에 자세히 나와있는데...윽 뭐더라? ) 그거보다 최소한 비슷한 러닝타임을 보이지 않을까 하는데..흠... 점이 n개면... 쩝..단순하지가 않군요. 어쩔수없이 stack같은 데이터를 써서 저장해야 할것같군요. n개일경우는 없었던것으로 합시다. 우히히.. ps.아참 도미노문제..제가 틀렸군요. ^^ 어떤분께서 증명을 해주셨는데 제가볼때는 induction으로 증명을 쉽게 줄일수 있겠네요. 아니면 다음과 같은 증명방법도 생각해볼수있겠군요. (0,0) --> (a,b) 라는 lattice point traverse 하는 알고리듬으로 고칩니다. 이경우 (x_n,y_n) 을 traverse 하는 포인트들이라고 할때 x_n increasing y_n increasing하게 만든다면 각각의 (x_n,y_n) 에선 반드시 하나나 두개의 passible path가 존재합니다. ( traverse 는 반드시 edge of sub rectangle of size c*d ) 이렇게 하면 위의문제를 임의의 직사각형 a*b를 임의의 직사각형 c*d로 cover 할수있느냐 없느냐의 문제로 바뀝니다. path는 반드시 x=a or y=b라는 boundary 하고 만나야 합니다. 대충 induction으로 둘중 한변이 정수배임을 증명할수 있겠군요. 1010101010101010101010101000000010101010010101010101000000010001111110101001010 0101010011111010101000100010110101010101010101001010101010101010101111111101010 1011111100010101010101010101101010101011111101010111101010001110101010001010110 http://www.math.mcgill.ca/~chung |