[백준] 20149번 - 선분 교차 3 (Platinum 4)
업데이트:
문제 링크
백준 20149번 - 선분 교차 3 (Platinum 4)
문제 설명
2차원 평면 상의 선분 두 개가 주어져있을 때, 선분들이 교차하는지 여부를 출력한다.
두 선분이 일치하거나, 선분의 끝 점이 다른 선분 위에 있는 것도 교차하는 것으로 간주한다.
두 선분이 한 점에서 교차한다면, 교차점도 출력한다.
정답 코드 및 설명
백준 17387번 - 선분 교차 2 (Gold 2) 문제에서 교차점을 직접 구하는 과정이 추가되었다.
선분의 길이가 항상 양수라는 조건이 있으므로, 사실 선분의 길이가 0인 부분은 빼도 정답이 된다.
직선의 교차점을 구하는 것은 사실 일차 연립 방정식을 푸는 것과 같다.
하지만 이 문제는 선분의 교차점을 구하는 것이므로, 경우를 더 나누어야 한다.
구체적인 경우의 수는 아래와 같다.
- 두 직선이 나란할 때(교점은 없음)
- 일차 연립 방정식의 해가 없을 때이다.
- 계수들로 이루어진 행렬의 행렬식은 0이다.
- $(x_3, y_3)$가 $(x_1, y_1), (x_2, y_2)$를 지나는 직선 위에 없다.
- 두 직선이 일치할 때
- 일차 연립 방정식의 해가 무수히 많을 때이다.
- 계수들로 이루어진 행렬의 행렬식은 0이다.
- 네 점이 한 직선 위에 있는 경우로, 아래 세 가지 경우로 세분화시킬 수 있다.
- 교점이 무수히 많은 경우 : 두 선분의 교집합이 선분이다.
- 교점이 아예 없는 경우
- 교점이 단 하나인 경우 : 한 선분의 끝점이 다른 선분의 시작점이다.
- 두 직선의 교차점이 한 개일 때
- 일차 연립 방정식의 해가 단 하나인 경우이다.
- Cramer’s rule로 해를 구할 수 있다.
- 구한 교차점이 두 선분 위의 점인지는 따로 체크해주어야 한다.
이를 구현한 구체적인 코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import java.io.*;
import java.util.StringTokenizer;
public class BOJ20149 {
private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private long[][] points = new long[4][2];
private long[][] coeff;
private long[] constant;
private void input() throws IOException {
StringTokenizer st1 = new StringTokenizer(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
points[i / 2][i % 2] = Integer.parseInt(st1.nextToken());
points[i / 2 + 2][i % 2] = Integer.parseInt(st2.nextToken());
}
}
private void setLinearEq() {
coeff = new long[][] {{points[1][1] - points[0][1], points[0][0] - points[1][0]},
{points[3][1] - points[2][1], points[2][0] - points[3][0]}} ;
constant = new long[] {points[0][0] * points[1][1] - points[1][0] * points[0][1],
points[2][0] * points[3][1] - points[3][0] * points[2][1]};
}
private boolean isParallel() {
return det(coeff) == 0;
}
private long[][] solveEquation() {
long[][] ans = new long[2][2];
ans[0][0] = det(new long[][] {{constant[0], coeff[0][1]}, {constant[1], coeff[1][1]}} );
ans[1][0] = det(new long[][] {{coeff[0][0], constant[0]}, {coeff[1][0], constant[1]}} );
ans[0][1] = ans[1][1] = det(coeff);
return ans;
}
private long det(long[][] matrix) {
return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
}
private class Cross {
int isCross;
Point point;
class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
Cross(boolean isCross) {
if (isCross) this.isCross = 1;
else this.isCross = 0;
this.point = null;
}
Cross setPoint(double x, double y) {
point = new Point(x, y);
return this;
}
}
private Cross overlap(long p0, long p1, long p2, long p3) {
if (Math.max(p0, p1) < Math.min(p2, p3) || Math.max(p2, p3) < Math.min(p0, p1))
return new Cross(false);
if (Math.max(p0, p1) > Math.min(p2, p3) && Math.max(p2, p3) > Math.min(p0, p1))
return new Cross(true);
return new Cross(true).setPoint(0, 0);
}
private boolean isIn(long p0, long p1, long p) {
return (p <= p0 && p1 <= p) || (p <= p1 && p0 <= p);
}
private Cross cross() {
// 선분 하나가 사실 점인 경우
if (points[0][0] == points[1][0] && points[0][1] == points[1][1]) {
if (coeff[1][0] * points[0][0] + coeff[1][1] * points[0][1] == constant[1] &&
isIn(points[2][0], points[3][0], points[0][0])
&& isIn(points[2][1], points[3][1], points[0][1]))
return new Cross(true).setPoint(points[0][0], points[0][1]);
return new Cross(false);
}
if (points[2][0] == points[3][0] && points[2][1] == points[3][1]) {
if (coeff[0][0] * points[2][0] + coeff[0][1] * points[2][1] == constant[0] &&
isIn(points[0][0], points[1][0], points[2][0])
&& isIn(points[0][1], points[1][1], points[2][1]))
return new Cross(true).setPoint(points[2][0], points[2][1]);
return new Cross(false);
}
// 두 직선이 평행한 경우
if (isParallel()) {
// 경우 1 : 두 직선이 나란한 경우(교점 X)
if (coeff[0][0] * points[2][0] + coeff[0][1] * points[2][1] != constant[0])
return new Cross(false);
// 경우 2 : 두 직선이 같은 경우
// 직선이 y축과 평행하지는 않은 경우
Cross answer;
if (points[0][0] != points[1][0]) {
answer = overlap(points[0][0], points[1][0], points[2][0], points[3][0]);
if (answer.point == null) return answer;
// points[0]이 유일한 겹치는 점
if (points[0][0] == points[2][0] || points[0][0] == points[3][0])
return answer.setPoint(points[0][0], points[0][1]);
// points[1]이 유일한 겹치는 점
return answer.setPoint(points[1][0], points[1][1]);
} else { // 직선이 y축과 평행한 경우
answer = overlap(points[0][1], points[1][1], points[2][1], points[3][1]);
if (answer.point == null) return answer;
// points[0]이 유일한 겹치는 점
if (points[0][1] == points[2][1] || points[0][1] == points[3][1])
return answer.setPoint(points[0][0], points[0][1]);
// points[1]이 유일한 겹치는 점
return answer.setPoint(points[1][0], points[1][1]);
}
}
// 두 직선이 평행하지 않은 경우
long[][] cross = solveEquation();
if (isIn(points[0][0] * cross[0][1], points[1][0] * cross[1][1], cross[0][0])
&& isIn(points[0][1] * cross[0][1], points[1][1] * cross[1][1] , cross[1][0])
&& isIn(points[2][0] * cross[0][1], points[3][0] * cross[1][1], cross[0][0])
&& isIn(points[2][1] * cross[0][1], points[3][1] * cross[1][1], cross[1][0])) {
return new Cross(true).setPoint((double)cross[0][0] / cross[0][1], (double)cross[1][0] / cross[1][1]);
}
return new Cross(false);
}
private void print() throws IOException {
StringBuilder sb = new StringBuilder();
Cross cross = cross();
sb.append(cross.isCross).append('\n');
if (cross.point != null)
sb.append(cross.point.x).append(' ').append(cross.point.y);
bw.write(sb.toString());
bw.close();
}
private void solution() throws IOException {
input();
setLinearEq();
print();
}
public static void main(String[] args) throws IOException {
new BOJ20149().solution();
}
}
댓글남기기