기하학

[BOJ/JAVA] 16958번: 텔레포트

16958번: 텔레포트https://www.acmicpc.net/problem/16958키워드2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.구현두 도시 간 거리를 전부 계산하여 cityMatrix에 저장한다.만약 두 도시가 특별한 도시라면 T와 비교하여 더 작은 시간을 저장한다.플로이드-워셜 알고리즘을 이용하여 최소 이동 시간을 구하자.코드import java.io.BufferedRead..

[BOJ/JAVA] 1198번: 삼각형으로 자르기

1198번: 삼각형으로 자르기https://www.acmicpc.net/problem/1198키워드볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.구현문제에서는 삼각형을 계속 제거해 나갔지만 결국은 볼록 다각형의 3점으로 만들 수 있는 삼각형 넓이의 최댓값과 동일한 문제이다.N개의 점에서 3개를 선택하여 해당 삼각형의 넓이의 최댓값을 ..

[BOJ/JAVA] 1711번: 직각삼각형

1711번: 직각삼각형https://www.acmicpc.net/problem/1711키워드2차원 평면에 N개의 점이 주어져 있다. 이 중에서 세 점을 골랐을 때, 직각삼각형이 몇 개나 있는지를 구하는 프로그램을 작성하시오.구현한 점을 기준으로 다른 두 점을 향한 벡터의 내적이 0이면 직각임을 이용한다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class java_..

[BOJ/JAVA] 11758번: CCW

11758번: CCWhttps://www.acmicpc.net/problem/11758키워드2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.구현P1P2 벡터와 P2P3 벡터의 외적을 이용하여 계산한다.두 벡터의 외적이 0이면 일직선이다.두 벡터의 외적이 양수면 시계방향이다.두 벡터의 외적이 음수면 반시계방향이다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_11758 { s..