공부공간

https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 첫 시작점으로 부터 목적지(2) 까지 갈 수 있는지 확인한다 (bfs) 탐색전 마네킹거리(K, 마네킹 좌표에서 bfs로 k번이동하여 갈수있는곳)를 불가능 표시를 해두고 한번만 BFS를 진행하면 해결된다. import java.io.BufferedReader; import java.io.IOException; import ja..

오목/볼록 다각형을 판단하기위한 알고리즘으로 CCW를 사용한다. CCW가 잘 설명되어 있는글은 https://jason9319.tistory.com/358 CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자 jason9319.tistory.com 이글을 판단하면 된다. Z=0인 두 벡터를 연결한다면, 1 > 2 > 3 순서의 ccw값이 ( z=0 인 외적값 ) 양수면 반시계방향에 위치에있다 0이면 일직선상에있다 ( 외적으로 만드는 평행사변형의 넓이값이 0이라는뜻) 음수면 시계방향으로 세점이 위치..