C++
-
[기하학] 선분 교차1 (17386) (C++)BOJ C++ 알고리즘 공부 2022. 2. 15. 18:07
https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제. 2. 입출력 3. 문제 풀이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다. CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시계 방향, 반시계 방향 또는 평행하게 놓여있는지 여부를 알 수 있다. ty..
-
[기하학] CCW(11758) (C/C++)BOJ C++ 알고리즘 공부 2022. 2. 12. 16:23
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어질때 이를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 문제. 2. 입출력 3. 문제 풀이 첫번째, 두번째 점을 이용하여 직선의 방정식을 구하고, 세번째 점을 방정식에 대입했을 때 양수가 나오면 반시계 방향, 음수가 나오면 시계 방향, 0이 ..
-
[기하학] 두 원(7869) (C++)BOJ C++ 알고리즘 공부 2022. 2. 11. 19:19
https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 1. 문제 개요 2차원 평면상에 두 원이 주어질 때, 교차하는 영역의 넓이를 소수점 셋째자리 구하는 문제. 2. 입출력 3. 문제 풀이 두 원이 만나는 경우는 네가지로 나눌 수 있다. 첫번째는 두 원이 만나지 않는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반지름을 합한 값보다 크다. 두 원이 교차하는 영역이 존재하지 않게 된다. 두번째는 한 원이 다른 원에 포함되지 않으면서 한 점에서 만나는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반..
-
[기하학] 다각형의 넓이(2166) C++BOJ C++ 알고리즘 공부 2022. 2. 10. 00:38
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 1. 문제 개요 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 주어질 때, 이 다각형의 면적을 구하는 문제. 2. 입출력 3. 문제 풀이 다각형을 이루는 순서대로 점이 주어지므로 신발끈 공식을 사용해서 해결할 수 있다. 4. 전체 코드 #include #include #include #include using namespace std; //다각형의 넓이 int main(){ vector v; ..
-
[플로이드-와샬] 운동(1956)BOJ C++ 알고리즘 공부 2022. 2. 7. 23:38
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 문제 개요 1번부터 V번 마을이 있을 때, 시작점으로 돌아오는 사이클 중 가중치 합의 최솟값을 찾는 문제. 예를 들어 입력 값이 다음과 같이 주어질때, 3 4 //정점수, 간선수1 2 1 3 2 11 3 5 // 1에서 3로 가는 노드의 가중치가 52 3 2 2 -> 3 -> 2 3 -> 2 -> 3 위와 같이 두 개의 사이클이 만들어질 수 있고 가중치 합의..
-
[자료구조] 이진 검색 트리(5639)BOJ C++ 알고리즘 공부 2022. 2. 3. 23:48
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 1. 문제 개요 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제. 이진 검색 트리란, 노드의 왼쪽 서브트리에 있는 모든 노드의 키가 노드의 키보다 작고 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크며, 왼쪽, 오른쪽 서브트리도 이진 검색 트리인 이진 트리를 말한다. 전위 순회는 루트-왼쪽-오른쪽 순으로 노드를 방문 후위..