본문 바로가기

기하학

 (28)
[Python] 3878번 점 분리 https://www.acmicpc.net/problem/3878 23/10/06  이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다. 흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다. 문제 접근 방식:  문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다. 검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다. 여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다. 볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다. 예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다. 한..
[Python] 31529번 2024년에는 혼자가 아니길 https://www.acmicpc.net/problem/31529 24/03/09  맷코 컵의 검수진으로 검수를 했던 문제 중 하나이다. 단순한 기하학 문제이다. 문제 접근 방식:  원점에서 $A$까지 떨어진 거리를 $a$, 원점에서 $B$까지 떨어진 거리를 $b$, 마찬가지로, $c, d$가 있다고 하자. 그러면 $\overline{AC}^{2} + \overline{BD}^{2} = X = a^2 + b^2 + c^2 + d^2$으로 나타낼 수 있다. 마찬가지로, $Y = (a+b)^2 + (c+d)^2 = a^2 + b^2 + c^2 + d^2 + 2ab + 2cd$으로 표현할 수 있다. $M$과 $N$의 좌표는 $\frac{a-b}{2}$와 $\frac{c-d}{2}$이므로, $\overline..
[Python] 30912번 위잉위잉 https://www.acmicpc.net/problem/30912 24/05/11  각도 정렬을 "잘" 구현해야 되는 문제이다. 문제 접근 방식:  처음으로 접근했던 방식은 파이썬 math모듈의 atan2함수를 이용한 정렬이다. 파이썬 공식 도큐먼트에 나와있는 atan2함수의 설명은 다음과 같다.math.atan2(y, x)Return atan(y / x), in radians. The result is between -pi and pi. The vector in the plane from the origin to point (x, y) makes this angle with the positive X axis. The point of atan2() is that the signs of both inp..
[Python] 11668번 파이프 청소 https://www.acmicpc.net/problem/11668 24/05/12  기하학 + 그래프 이론 관련 문제이다. 좋은 문제인 것 같아서 풀이를 남겨보려고 한다. 문제 접근 방식:  문제에서 요구하고 있는 바를 정리해보자. 1. 파이프는 수원지와 도시를 잇는다.2. 두 파이프는 서로 교차할 수 있으며, 한 교차점에는 세 파이프가 동시에 교차하지 않는다.3. 교차점에는 이물질이 끼는데, 한 파이프에 로봇을 넣으면 그 파이프의 교차점을 모두 청소해 줌.4. 로봇이 충돌하는 일을 방지하기 위해 교차점에는 오직 하나의 파이프에만 로봇이 있어야 함.5. 어떤 파이프의 부분 집합을 잡아서 동시에 로봇을 투입했을 때, 두 로봇이 충돌하는 일이 없으면서 모든 교차점을 청소할 수 있는지를 판단해야 함.6. 두..
[Python] 1708번 볼록 껍질 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 23/10/02 기하 알고리즘 중 대표적인 알고리즘, 볼록 껍질 알고리즘을 연습할 수 있는 좋은 문제이다. 이 문제를 통해 볼록 껍질을 구현하는 템플릿 코드를 구성하면 좋을 것이다. 문제 접근 방식: 일반적으로 볼록 껍질을 구현하는 데에는 두 가지 방법이 존재한다. 이 문제의 해설에서는 두 가지 방법 모두 소개할 것이다. 첫번째 방법은 그라함 스캔이다. 그라함 스캔의 원리는 간..
[Python] 22770번 Ellipse Intersection https://www.acmicpc.net/problem/22770 22770번: Ellipse Intersection Input may contain multiple test cases. The first line is a positive integer n (n ≤ 100), denoting the number of test cases below. Each case is composed of two lines, the first one is the description of orbit A, and the second one the description of orbit www.acmicpc.net 22/12/31 전형적인 수학문제로, 극좌표로 적분을 해야하는 문제이다. 극좌표 적분에 관한 내용은 미적분학..
[Python] 7869번 두 원 https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 22/11/09 전형적인 수학, 기하학 문제로, 제2코사인 법칙을 사용하여 문제를 해결할 수 있다. 문제 접근 방식: 이 문제를 풀기 위해서는 먼저 제2코사인 법칙을 알아야 한다. 제2코사인 법칙이란, 어떤 삼각형의 세 변과 그 대각 사이에 성립되는 관계로, 위와 같은 식을 따른다. 따라서, 내가 예를 들어, 각 B를 구하고 싶으면 저 식 중 2번째 식을 변형하여 아래와 같이 구할 수 있다. 이 식을 이용할 것이다. 먼저, 원의 위치 관계에 따라 3가지 경우로 나..
[Python] 16958번 텔레포트 https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 22/10/27 다양한 풀이가 존재하는 문제로, 파이썬으로 풀기 위해서는 별의별 최적화를 다 해야 되는 문제이다. 나이브한 플로이드-워셜 알고리즘으로 접근한다면 파이썬에서는 TLE를 받을 수밖에 없기 때문에 무조건적인 최적화가 필요하다. 이 글에서는 2가지 풀이 방법을 소개할 것이다. 첫 번째 문제 접근 방식: 이 문제를 먼저 접했을 때, 도시의 수의 ..

티스토리툴바