동고 팔자 상팔자

- 문제 : www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net MST 문제

문제 : www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬 문제입니다.

문제 : www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 위상정렬 문제입니다.

문제 : www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상정렬 문제입니다.

문제 : www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 인덱스트리 문제입니다.

유니온파인드 집합연산 시 사용하는 유니온파인드 코드 disjoint-set이라고도 불림 합집합 시, 부모에 값이 계속 더하면 합집합 개수까지 확인할 수 있다.

회전하는 캘리퍼스(Rotating calipers) 가장 먼 두점의 거리 구할때 사용하는 알고리즘 컨벡스헐을 구한 다음에 수행해야한다. 자세한 원리는 위키(https://en.wikipedia.org/wiki/Rotating_calipers)에서 확인할 수 있다. 컨벡스헐 전체 거리를 볼 필요가 없기 때문에 빠르다. 자바로 구현한 코드

컨벡스헐 기준점 잡기 -> 정렬 -> 컨벡스헐 만들기

두 직선의 교점 구하기 분모 (x1−x2)(y3−y4)−(y1−y2)(x3−x4)=0이면 기울기가 같은것이기 때문에 두 직선은 평행 또는 일치함