CCW7 [백준] 12781번 - PIZZA ALVOLOC [Java] https://www.acmicpc.net/problem/12781 1. 아이디어 피자를 네 조각으로 나누려면 두 선분이 서로 교차해야한다는 점에서 선분 교차 유형임을 파악하고 CCW 알고리즘을 활용해서 사이 좋게 피자를 나누어 먹을 수 있는지 파악했다.2. 문제풀이 네 점을 A, B, C, D 순서라고 할 때 선분 AC와 선분 BD가 만들어진다.여기서 선분 교차 판정을 하면 되는데 선분 AC에 대해 두 점이 선분의 반대쪽에 있어야 하고, 선분 BD에 대해 두 점이 선분의 반대쪽에 있어야 한다.이를 CCW에 적용하면 벡터 AC와 벡터 AB의 외적, 벡터 AC와 벡터 AD의 외적, 두 외적 벡터의 방향이 반대여야하고, 벡터 BD와 벡터 BA의 외적, 벡터 BD와 벡터 BC의 외적, 두 외적 벡터의 방향이.. 2024. 12. 8. [백준] 20149번 - 선분 교차 3 [Java] https://www.acmicpc.net/problem/20149 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 기존의 선분 교차 2 문제에서 교점이 하나만 존재할 경우 교점까지 출력하는 문제다.([코딩테스트 준비/백준] - [백준] 17387번 - 선분 교차 2 [Java]) 기존의 코드를 활용하기 위해 교점을 반환하는 메서드만 추가로 작성했는데 이 교점을 반환하는 과정이 상당히 까다로웠다. 먼저 교점이 없으면 null을 반환해서 구분하는 방식으로 구현했고 메서드 시작 부분에 교차하는지 여부를 CCW 알고리즘으로 빠르게 판단했다. 이후 두 선분에 대해 두 선분이 모두 y축에 평행한 경우(기울기가 없는 경우), 한 선분이 y축에 평행한 경우, 나머지 경우로 조건.. 2024. 12. 5. [백준] 17387번 - 선분 교차 2 [Java] https://www.acmicpc.net/problem/17387 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 세 점, 네 점이 일직선 위에 있을 수 있어서 조건 분기가 좀 까다로웠다.먼저 네 점이 일직선 위에 있는 경우, 세 점이 일직선 위에 있는 경우, 나머지 경우로 나누었다. 네 점이 일직선 위에 있는 경우 두 선분이 겹치는 경우가 있는지 판단해야한다. 이때는 각 점의 좌표 관계로 겹치는지 판단할 수 있는데 포함관계일 때, 적당히 겹칠 때, 한 점만 겹칠 때 어떻게 조건을 나눠야 할지 고려해야 한다. 세 점이 일직선 위에 있는 경우에는 CCW에서 기준 벡터가 됐던 선분에 나머지 한 점이 포함되는지 판단하면 된다. 나머지 경우 기존의 선분 교차 1 문제처럼.. 2024. 12. 5. [백준] 17386번 - 선분 교차 1 [Java] https://www.acmicpc.net/problem/17386 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 세 점이 일직선 위에 있는 경우가 없으므로 L1에서 L2의 두 점에 대한 외적 벡터의 방향이 다르고, L2에서 L1의 두 점에 대한 외적 벡터의 방향이 다르면 두 선분이 교차한다는 점을 이용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2024. 12. 5. [백준] 1064번 - 평행사변형 [Java] https://www.acmicpc.net/problem/1064 1. 아이디어 삼각형을 만들 수 있는지 여부는 CCW 알고리즘을 활용해서 구했고, 평행사변형 둘레의 길이의 차의 최댓값은 기존 삼각형의 각 변의 길이를 크기 순으로 a, b, c라고 했을 때, 가장 짧은 둘레의 길이는 2 * (a + b), 가장 긴 둘레의 길이는 2 * (b + c)라는 점을 이용했다.2. 문제풀이 세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 CCW의 값이 0인지 판단하는 방식으로 구현했다.둘레의 길이의 차는 위 수학적 테크닉으로 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void mai.. 2024. 12. 5. [백준] 1027번 - 고층 건물 [Java] https://www.acmicpc.net/problem/1027 1. 아이디어 현재 빌딩에서 특정 빌딩이 보이는지 여부를 CCW 알고리즘을 통해 구한 외적 벡터의 방향으로 알 수 있다는 점을 이용했다.2. 문제풀이 현재 빌딩의 지붕에서 특정 빌딩의 지붕이 보이는지 판단할 때 기준점에 대해 CCW를 통해 방향이 양의 값이면 보이는 빌딩이고 0이면 접하는 빌딩, 음이면 기준점에 가려진 빌딩이라는 점을 이용했다. 기준점은 현재 빌딩에 대해 빌딩의 바닥을 기준으로 하고 보이는 빌딩을 찾으면 해당 빌딩의 지붕으로 옮겨준다.보이는 빌딩에 대해 나중에 해당 빌딩에서 현재 빌딩을 비교할 때도 당연히 보이는 빌딩으로 판단하기 때문에 한번 확인하면 양쪽 모두 보이는 빌딩으로 체크를 해주고, 대신 현재 빌딩에서 오른쪽에.. 2024. 12. 5. [백준] 11758번 - CCW [Java] https://www.acmicpc.net/problem/11758 1. 아이디어 CCW 알고리즘을 구현만 하면 되는 문제로 벡터의 외적을 구하는 ccw 메서드를 작성해서 구현했다.2. 문제풀이 외적 벡터를 구한 이후 -1, 0, 1로 출력하기 위해 삼항 연산자와 절댓값을 구할 수 있는 Math.abs를 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTo.. 2024. 12. 5. 이전 1 다음
