좌표평면 위의 모든 점들에서 거리 합이 가장 가까운 점을 찾는 방법

https://atcoder.jp/contests/abc419/tasks/abc419_c C - King's SummitAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 좌표평면 위의 n개의 점들이 1초에 팔방향으로 움직이거나 멈춰있을 수 있다. 이때, 모든 점들이 하나의 점에 모인다고 할때, 걸리는 최단 시간을 구한다면? -----------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 기하학
• · 2025. 8. 18.
• textsms

벡터 (x,y)를 90도 회전하는 방법

1. 회전 행렬 벡터 (x,y)는 극좌표계를 이용하면 $(rcos \theta , rsin \theta)$   이 상황에서 A만큼 회전시킨다면... Q의 좌표는 $(rcos (\theta + A), rsin (\theta + A))$   삼각함수의 덧셈정리를 이용하면 $cos (\theta + A) = cos \theta * cosA - sinA * sin \theta $이고  $sin (\theta + A) = sin \theta * cos A + cos \theta * sin A$ $x = rcos \theta, y = rsin \theta$이므로 이를 대입하면... $x' = rcos (\theta + A) = x cos A - y sin A, y' = rsin (\theta + A) = ycosA..

• format_list_bulleted 기하학
• · 2024. 11. 16.
• textsms

평면 위 두 직사각형이 서로 겹치는 직사각형의 좌표 구하는 놀라운 방법

두 직사각형의 왼쪽 하단 좌표, 오른쪽 상단 좌표 (x1,y1), (x2,y2), (x3,y3), (x4,y4)가 각각 주어질때, 이 두 직사각형이 서로 겹쳐서 생기는 영역의 좌표를 구해본다면?   E의 좌표가 (x5,y5), F의 좌표가 (x6,y6)라고 한다면... 놀랍게도 이를 구하는 공식이 있다 x5 = max(x1,x3)y5 = max(y1,y3) x6 = min(x2,x4)y6 = min(y2,y4) 만약 x5 > x6이거나 y5 > y6이면 두 직사각형이 겹치지 않는다 근데 몇개 해보니까 진짜 맞는듯? 왼쪽 하단은 max, 오른쪽 상단은 min     조건 하나하나 생각해서 할려고 하면 거의 무조건 틀리더라 그냥 공식 써버리는게 제일 편함 #직사각형1 (x1,y1), (x2,y2)#직사각형2..

• format_list_bulleted 기하학
• · 2024. 8. 29.
• textsms

사각형과 원이 겹치는 영역의 좌표의 개수는 O(N)에 구할 수 있을까

21676번: Газон (acmicpc.net) 왼쪽 아래 (x1,y1), 오른쪽 위 (x2,y2)로 주어지는 사각형과 중심 (x3,y3), 반지름 r로 주어지는 원이 서로 겹치는 영역의 정수 점 (x,y)의 개수를 구하는 문제 정말 단순하게 생각하면 사각형 안의 모든 정수 점 (x,y)에 대하여 원의 방정식 내부 (x-x3)**2 + (y-y3)**2  def check(x,y): v = (x-x3)**2 + (y-y3)**2 if v   하지만 x1,x2,y1,y2,x3,y3의 범위가 -10만~10만이라 $O(N^{2})$은 시간초과가 날수밖에 없다 하지만... 이것말고 방법이 있나? x를 정했으면 그거에 대해 y는 모든 범위를 돌아봐야할텐데..? 방법은 원의 방정식은 (x-x3)..

• format_list_bulleted 기하학
• · 2024. 8. 1.
• textsms

원 안에 원을 가득 채우는 문제?(circle packing in a circle)

20744번: Cucumber Conundrum (acmicpc.net) 반지름이 s인 원 모양의 샌드위치가 있고 반지름이 r인 원 모양의 피클이 n개 있는데  이 피클을 샌드위치 위에 최대한 많이 높고 싶다 이 때 샌드위치 면적의 최대 z%까지만 놓을 수 있고 두 피클이 서로 겹치지 않아야한다 최대 몇개의 피클을 놓을 수 있는가? 샌드위치의 면적이 $\pi * s^{2}$이고 이것의 최대 z%가 피클 x개의 넓이 $\pi * r^{2} * x$이므로 $$\pi * s^{2} * \frac{z}{100} >= \pi * r^{2} *x $$ 식을 정리하면 $x  사실 이것만 만족하면 되는줄 알았는데... 아니더라고 https://en.wikipedia.org/wiki/Circle_packing_in_a_..

• format_list_bulleted 기하학
• · 2024. 7. 27.
• textsms

꼭짓점이 둥근 볼록껍질(round convex hull)의 둘레의 길이를 구하는 법

1. 문제 10903번: Wall construction (acmicpc.net) 10903번: Wall construction 첫 번째 줄에는 두 개의 자연수 N, R (1 ≤ R ≤ 100)이 공백으로 구분되어 주어진다. N은 기둥의 개수이며, R은 기둥의 반지름으로 모든 기둥은 같은 반지름을 가진다. 이후 N개의 줄에는 미술관의 www.acmicpc.net 2. 풀이 convex hull의 둘레의 길이를 구해야하는데.. 단순히 둘레의 길이만 구한다면.. convex hull의 모든 꼭짓점을 찾고 꼭짓점끼리 거리를 합하면 그만이지만 이 문제는 꼭짓점이 둥근 형태라는게 문제다. convex hull의 꼭짓점을 찾고 꼭짓점끼리 거리를 구한다음, 파란색으로 동그라미 된 둥근 부분의 길이도 구해야한다 이를 ..

• format_list_bulleted 기하학
• · 2023. 9. 27.
• textsms