사각형과 원이 겹치는 영역의 좌표의 개수는 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

다각형 내부의 격자점 수를 셀 수 있을까 - 픽의 정리(pick's theorem) + (선분에 있는 격자점의 개수 세는 방법)

1. 픽의 정리(pick's theorem) 좌표가 모두 정수인 점을 격자점(lattice)이라고 부른다. 2차원 좌표평면에서 모든 꼭짓점이 격자점인 다각형이 자기 자신이 교차하지 않을때(not self-interaction), 넓이가 A이고 내부에 있는 격자점의 개수가 I이며 둘레(변)에 있는 격자점의 개수가 B이면... $$A = I + \frac{B}{2} - 1$$ 이 성립한다. 여러 경우의 수로 나눠서 증명하는데, 조금 까다롭다... 읽어보는걸로 만족하고 생략 https://www.youtube.com/watch?v=GTeZd_IdcoY 영상이 설명을 잘해주고 있는데... 주어진 다각형을 내부의 격자점 수가 0개이고 경계선 위 격자점의 개수가 3개인 삼각형으로 도형을 모두 분할할 수 있고, 이 삼..

• format_list_bulleted 기하학
• · 2023. 8. 31.
• textsms

체스판에서 정사각형의 개수

1. 문제 n개의 점이 일정한 간격으로 각 줄마다 n개의 줄이 존재하는 n*n 체스판이 있다고 하자. n*n 체스판에서 서로 다른 네개의 점을 이어 만든 정사각형의 개수는 몇개일까? 선분을 이을 때 선분 중간에 존재하는 점은 개수로 세지 않는다. 예를 들어 n=3이면 6개 존재하고 n=4이면 20개 존재한다. n은 2 이상의 자연수 2. 풀이 이런 문제가 나오면 규칙이 있겠구나 이렇게 생각하고 규칙을 찾으면 된다 프로그래밍을 해서 정사각형을 일일이 세도록 만들수는 없을거니까 근데 사실 규칙을 찾을려면 정사각형의 개수를 정확하게 세야하는데 그것이 절대 쉬운건 아니다 규칙을 찾겠다는 생각부터 한 것이 분명 한단계 발전한거 2가지로 나눠 생각할 수 있다 빨간색으로 된 격자형 정사각형이랑 파란색으로 된 기울어진..

• format_list_bulleted 알고리즘 일반
• · 2021. 11. 22.
• textsms