[최소 공통 조상 단계] 백준 17435번 합성함수와 쿼리
문제 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오. 입력 첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000) 다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다. 다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000) 다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m) 출력 주어지는 n, x마다 fn..
[수학 4 단계] 백준 2162번 선분 그룹
문제 N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다. 두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다. N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자. 입력 첫째 줄에 N(1≤N≤3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사..
[수학 4 단계] 백준 17387번 선분 교차 2
문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 경우이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력 L1과 L2가 교차하면 1, 아니면 0을 출력한다. 제한 -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000 이 문제는 3점이 일직선 일 수도 있음. A와 B중 큰 것을 B, C와 D중 큰 것을 D라고 할 때 A가 D보다 작으면서 C..
[수학 4 단계] 백준 17386번 선분 교차 1
문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. 출력 L1과 L2가 교차하면 1, 아니면 0을 출력한다. 제한 -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000 이 상황이 되려면 CDA의 방향과 CDB의 방향이 반대가 되어야 함. 이는 위에서도 성립하므로 ABC와 ABD도 반대면 교차 하지만 이것은 어떤 3점도 일직..
[수학 4 단계] 백준 11758번 CCW
문제 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. 출력 P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다. 다각형 넓이 구하기에서 사용한 | (xi * yi+1) - (yi * xi+1)|/2 , 0 > arr[i].first >> arr[i].sec..
