C언어
-
[플로이드-와샬] 케빈 베이컨의 6단계 법칙(1389) (C++)BOJ C++ 알고리즘 공부 2022. 2. 27. 17:22
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 1. 문제 개요 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 예를 들어, 1이 2와 아는 사이이고 2가 3과 아는 사이, 3과 4는 아는 사이이면 1과 4는 3단계만 거치면 된다. 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이..
-
[기하학] 선분 교차 3 (20149) (C++)BOJ C++ 알고리즘 공부 2022. 2. 17. 19:21
https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 1. 문제 개요 2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제. 선분 교차 2 문제와 같지만 선분이 한 점에서 만나는 경우 점의 좌표를 출력하는 문제. 2. 입출력 3. 문제 풀이 선분 교차 1 문제와 같이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다. CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다. 세 개의 점이 시..
-
[기하학] 두 원(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. 문제 풀이 두 원이 만나는 경우는 네가지로 나눌 수 있다. 첫번째는 두 원이 만나지 않는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반지름을 합한 값보다 크다. 두 원이 교차하는 영역이 존재하지 않게 된다. 두번째는 한 원이 다른 원에 포함되지 않으면서 한 점에서 만나는 경우이다. 이 경우에는 두 원의 중심의 거리가 두 원의 반..