To Paint a World

https://www.acmicpc.net/problem/1077 1. 문제 정의두 볼록 다각형이 주어지면, 겹쳐진 부분의 넓이를 구하는 문제이다. 볼록 다각형 내 점은 반시계 방향 순서대로 주어지며, 각 꼭짓점은 다른 볼록 다각형의 변 위에 있지 않다. 2. 예제 분석문제를 풀어보기에 앞서, 입력에서 주어진 볼록 다각형들의 형태와 배치를 직접 그려서 확인해 보자.소스 코드 ( matplotlib 필요) 를 통해 예제를 시각화할 수 있다.  예제X  예제 1, 4번은 두 다각형이 교차하며 새로운 영역을 만들어내고 있고,예제 2번은 한 다각형이 다른 다각형 내에 완전히 포함되어 있으며예제 3번은 두 다각형이 서로 교차하는 영역이 존재하지 않는다. 예제 1, 3, 4번에서 서로 겹치는 다각형을 확인해봤을 때..

https://www.acmicpc.net/problem/14266 1. 문제 정의n개의 선분이 주어진다. 원점을 지나는 직선을 그었을 때, 최대 몇 개의 선분과 교차할 수 있는지 구하는 문제이다.   원점으로부터 기울기가 $ 1 $인 직선을 그었을 때 주어진 모든 선분과 교차할 수 있기 때문에, 예제 입력1 의 답은 3이 된다.  2. 풀이 원점을 지나는 직선은 (0, inf) 범위 내의 기울기를 가질 수 있다. 그러나 실수 범위를 모두 탐색하는 것은 불가능하다.교차하는 선분의 개수는 직선이 선분의 꼭짓점을 지날 때만 변화한다. 따라서, 각 꼭짓점과 원점을 이은 선분의 기울기에 대해서만 교차 선분의 개수를 확인하면 된다.  문제의 예제에서는 기울기가 각각 $ \frac{1}{4} $, $ 1 $, $ ..

https://www.acmicpc.net/problem/161351. 문제 정의  두 직사각형의 꼭짓점의 좌표가 순차적으로 주어졌을 때, 아래 수식이 성립하는 방향 벡터 $ \vec{ u} $ 가 존재하는지를 확인해야 한다. $$ | \vec{d} \cdot \vec{u} | \geq | \vec{ A_1 } \cdot \vec{u }  | + | \vec{ A_2 } \cdot \vec{ u } |  + | \vec{ B_1 } \cdot \vec{ u } |  + | \vec{B_2} \cdot \vec{u} | $$ 2. 풀이2-1. 문제 시각화문제에서 주어진 두 직사각형과, 각도가 ($ 0 $, $\pi$ ) 범위 내에 존재하는 단위 벡터를 부등식의 좌항과 우항에 대입시켰을 때의 값을 그래프로 ..

https://www.acmicpc.net/problem/7007 1. 문제 정의다음과 같은 좌표계가 설정되어 있다고 가정하자. y축이 위를 가리키고, z축의 방향은 스크린으로부터 멀어지는 방향이다.관찰자 (viewer) 는 (0, 0, -∞) 에 존재한다.  xz 평면 위 오브젝트들의 목록과 y 축에 평행한 평면들의 목록이 입력으로 주어진다.각 평면은 오브젝트 공간을 두 개로 분할한다. 관찰자(0, 0, -∞) 가 포함된 공간과 포함되지 않은 공간이다. 예제 입력1 로 주어진 입력을 좌표공간에 나타내보면 다음과 같다. 두 점 (159, 165), (-131, -177) 을 관통하고 y축에 평행하는 첫 번째 평면에 의해,오브젝트 공간이 {B, C, G, E, J} 의 공간과 {A, D, F, H , I}..

https://www.acmicpc.net/problem/31383 1. 문제 정의3 x 3 의 회전 행렬이 주어졌을 때, 회전행렬의 회전축과 회전각을 구한다. 풀이 1. 선형대수학 기반 풀이1-1. 회전 행렬 분석https://www.youtube.com/watch?v=SzqRLZIolJU 2차원 회전행렬을 고윳값분해하면 회전에 해당되는 복소수가 eigenvalue 로 나온다.2차원 회전행렬을 3차원에서 생각해보면, z축을 기준으로 잡고 회전을 하게 된다. 이를 고려하여 2차원 행렬을 3차원으로 확장하면 다음과 같이 나타낼 수 있다. $$ \begin{pmatrix} \cos (t) & \sin (t)  & 0 \\ -\sin (t) & \cos (t) & 0 \\ 0 & 0 & 1 \\ \end{pm..