| [ QuizWit ] in KIDS 글 쓴 이(By): parsec ( 먼 소 류 ) 날 짜 (Date): 2002년 4월 9일 화요일 오전 09시 12분 08초 제 목(Title): Re: 등적세모수 (미심쩍은 결과가 있어서 이리저리 고쳐봤는데 이제 맞게 된 듯..) 삼각형의 각 꼭지점이 x= i*u + j*v; i,j>=0, 0<=i+j<=n-1, u:↙, v:↘ (단위벡터) 라고 표현되고, 꼭지점 a,b,c로 구성되는 삼각형이 있으면, a = ia*u + ja*v b = ib*u + jb*v c = ic*u + jc*v a ≠ b ≠ c 라고 쓸 수 있고 이 때 삼각형의 넓이는 |(ib-ia)(jc-ja)-(jb-ja)(ic-ia)| n^2-1 개의 점에서,어차피 두 개 이상의 점이 같으면 면적이 0이므로 count하지 않기로 하고, 중복되는 경우는 나중에 3! 로 나눠주기로 하고, #include <stdlib.h> extern int flag_etn_calc_fin; int equimetric_triangular_number(int m, int n) { static int *num static int n_prev = 0; static int atot; int area; int ia, ja, ib, jb, ic, jc; if (!flag_etn_calc_fin || n_prev != n) { n_prev = n; atot = (n-1)*(n-1); num = malloc(sizeof(int)*(atot+1)); for(area=0; area<=atot; area++) num[area] = 0; for(ia=0; ia<n; ia++) for(ja=0; ja<n-ia; ja++) for(ib=0; ib<n; ib++) for(jb=0; jb<n-ib; jb++) for(ic=0; ic<n; ic++) for(jc=0; jc<n-ic; jc++) { area=abs((ib-ia)*(jc-ja)-(jb-ja)*(ic-ia)); if(area!=0) num[area]++; } for(area=0; area<=atot; area++) num[area]/=6; flag_etn_calc_fin = ~0; } return num[m]; } 초기 실행시간이 (n-1)^6 에 비례하는 무지막지한 루틴이지만... ◇ ~~~_ _ ∴ ~|~| | _/__, SEP. 11. 2001 _ ∴∴ _ ~ | | ＼ ` Armorica under a tat ,-| `,-,_| |__ | | | A ______|_|__|_|___|__|| | |__|_|_____________________________________ |