Circumcenter (추가중)
개요 Geometry 삼각형의 외심 구하기 접근 고등수학에서 외심의 정의부터 복습해보자. 외심은 세 꼭짓점으로부터의 거리가 같은 점이다. 정의를 바탕으로 점을 구해보자. 방식은 좌표로 노가다하는 법과 벡터를 이용하는 방법 (1), (2)가 있는데, 좌표 노가다부터 해보자. 내심은 좌표를 이용하는 방법에서 식이 너무 길어져서 포기했다. 벡터를 이용하는 방법을 읽어보면 내심도 쉽게 구할 수 있으니 잘 읽어보자. 1. 좌표 이용하기 점 A,B,C를 (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) 라고 하면, 외심 P(x,y,z)와 외접원의 반지름 R에 대해 다음이 성립한다. $(x-x_1)^2+(y-y_1)^2+(z-z_1)^2$ $=(x-x_2)^2+(y-y_2)^2+(z-z_2)^2$ $=(..
2023. 4. 8.
Barycentric, Trilinear coordinate
개요 Geometry 삼각형과 관련된 점을 나타내는 새로운 좌표체계 접근 Barycentric, Trilinear 고등수학에서 삼각형의 오심에 대해 배운다. 외심, 내심, 무게중심, 수심, 방심인데, 외심 내심 무게중심을 제외하고는 잘 쓰지 않는다. 외심과 내심 무게 중심을 벡터를 이용해 일반화하려면 생각할 부분이 많아지는데, 이때 좌표계를 새로 정의해 나타내면 생각이 쉬워진다. 편의상 외심, 내심, 무게중심을 각각 O, I, G라고 하자. Barycentric coordinate, 무게중심 좌표는 이름의 무게중심과 달리 G만 나타내는 것은 아니고, 삼각형 내부의 점 P에 대해 ▵BPC, ▵CPA, ▵APB의 넓이의 비를 나타내는 좌표이다. $\alpha:..
2023. 4. 8.
Freivald's algorithm
개요 Approximation, 확률론 A×B=C를 O(kN^2)에 해결하기 접근 기존의 행렬곱 일반적인 상황은 아니지만, 두 행렬의 곱이 다른 행렬과 같은지 확인해야 하는 상황이 있다. A×B=C를 검증한다고 가정하자. 만약 A,B,C의 크기가 각각 [p,m], [m,q], [p,q] 라면 곱셈 연산을 하는데 p×m×q번의 연산이 필요하고, 정수행렬 C를 만들기 위해 p×q×4 만큼의 메모리가 필요하다. 왜냐? 일반적으로 행렬곱 계산은 아래와 같이 해주기 때문이다. for (i = 0~p) for (j = 0~q) for (k = 0~m) C[i][j]+=A[i][k]*B[k][j] 크기가 100×100정도라면 큰 문제가 아니다. 하지만 1000이면 1e9번의 연산을 해야하고, 시간을 1분을 주지 않는..
2023. 3. 12.
