반평면의 교집합 넓이
다이아몬드 III의견: 0
평면 위에 \(N\)개의 반평면이 주어진다. \(i\)번째 반평면은 세 정수 \(a_i\), \(b_i\), \(c_i\)로 표현되며, 부등식 \(a_i x + b_i y \le c_i\)를 만족하는 모든 점 \((x, y)\)의 집합이다.
이 \(N\)개의 반평면을 모두 동시에 만족하는 점들의 집합, 즉 교집합 영역의 넓이를 구하여라. 교집합이 비어 있거나 넓이가 \(0\)(선분 또는 점)인 경우 답은 \(0\)이다.
각 반평면을 절반씩 잘라 나가며 영역을 관리하는 것은 \(O(N^2)\)이 되어 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(-10^6 \le a_i, b_i, c_i \le 10^6\)
\((a_i, b_i) \ne (0, 0)\)
첫 줄에 반평면의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 세 정수 \(a_i\), \(b_i\), \(c_i\)가 주어진다. \((a_i, b_i) \ne (0, 0)\)이다.
교집합 영역의 넓이를 출력한다. 절대 오차 또는 상대 오차가 \(10^{-4}\) 이하이면 정답으로 인정된다.
4
-1 0 0
1 0 2
0 -1 0
0 1 3
6.000000네 반평면은 각각 \(x\ge 0\), \(x\le 2\), \(y\ge 0\), \(y\le 3\)를 의미한다. 교집합은 가로 \(2\), 세로 \(3\)인 직사각형이므로 넓이는 \(6\)이다.
3
-1 0 0
0 -1 0
1 1 4
8.000000\(x\ge 0\), \(y\ge 0\), \(x+y\le 4\)의 교집합은 꼭짓점 \((0,0),(4,0),(0,4)\)인 직각삼각형으로 넓이가 \(8\)이다.
riseoj 작성
출처 Original
평가 및 의견
반평면의 교집합 넓이
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
반평면의 교집합 넓이