백준 3878 점 분리
23 Jun 2021https://www.acmicpc.net/problem/3878
흰 점과 검은 점이 주어졌을 때 두 점을 분리할 수 있는 직선을 그을 수 있는지를 파악하는 문제이다. 만약 흰 점으로 이루어진 컨벡스헐과 검은 점으로 이루어진 컨벡스헐을 각각 구한다고 하자.
그렇다면 두 점들을 분리할 수 없는 경우는 위의 2가지로 나타난다. 첫번째는 하나의 컨벡스헐 집합 내부에 다른 색깔 점이 존재하는 경우이다. 생각해보면 다각형 내부에 점이 존재할 경우 시계반대방향으로 다각형의 선분들에 대해서 내부의 점과 ccw를 하게되면 그 값은 항상 양수가 나올 것이다. 따라서 흰색 컨벡스 헐에 대해 검은색 컨벡스 헐에 속하는 점들을 모두 확인해주고 마찬가지로 색깔을 바꿔서 동일하게 진행하면 내부에 다른 색깔 점이 존재하는지 확인할 수 있다.
두번째는 점이 컨벡스 헐 선분 위에 존재하는 경우이다. 이 경우 ccw 결과가 0이 나오기 때문에 위에서 확인할 수 없다. 만약 ccw결과가 0이 나올 경우에도 분리할 수 없도록 하라! 라고 설정을 하게 되면 세번째 그림과 같은 상황에서 틀린 결과를 얻게 된다. 실제로는 분리할 수 있는데 같은 직선상에 존재한다고 판단해서 ccw값이 0이 나타나게 되기 때문이다. 이를 방지하기 위해 검은색 컨벡스 헐의 모든 선분과 하얀색 컨벡스 헐의 모든 선분 각각에 대해서 충돌여부를 확인해준다.
- 전체 코드
func ccw(a: (Int, Int), b: (Int, Int), c: (Int, Int)) -> Int {
let result = (b.0-a.0)*(c.1-a.1) - (b.1-a.1)*(c.0-a.0)
return result > 0 ? 1 : (result == 0 ? 0 : -1)
}
func dist(a: (Int, Int), b: (Int, Int)) -> Int {
let dx = a.0 - b.0, dy = a.1-b.1
return dx*dx + dy*dy
}
func check(a: (Int, Int), set: [(Int, Int)]) -> Bool {
let count = set.count
for i in 0..<count {
if ccw(a: set[i], b: set[(i+1)%count], c: a) <= 0 {
return false
}
}
return true
}
func notCrash(a1: (Int, Int), a2: (Int, Int), b1: (Int, Int), b2: (Int, Int)) -> Bool {
var A = a1, B = a2, C = b1, D = b2
if A > B {
swap(&A, &B)
}
if C > D {
swap(&C, &D)
}
let abc = ccw(a: A, b: B, c: C)
let abd = ccw(a: A, b: B, c: D)
let cda = ccw(a: C, b: D, c: A)
let cdb = ccw(a: C, b: D, c: B)
if abc == 0 && abd == 0 && cda == 0 && cdb == 0 {
return B < C || D < A
}
return !(abc*abd <= 0 && cda*cdb <= 0)
}
func makeHul(input: [(Int, Int)]) -> [(Int, Int)] {
var arr = input
arr.sort(by: {$0.1 < $1.1})
arr.sort(by: {$0.0 < $1.0})
let S = arr[0]
arr[1..<arr.count].sort(by: {
ccw(a: S, b: $0, c: $1) == 0 && (dist(a: S, b: $0) < dist(a: S, b: $1))
})
arr[1..<arr.count].sort(by: {
ccw(a: S, b: $0, c: $1) > 0
})
var stack:[(Int, Int)] = []
for next in arr {
while stack.count >= 2 && (ccw(a: stack[stack.count-2], b: stack[stack.count-1], c: next) <= 0) {
stack.removeLast()
}
stack.append(next)
}
return stack
}
let t = Int(readLine()!)!
var str = ""
for _ in 0..<t {
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var black:[(Int, Int)] = Array(repeating: (0, 0), count: n)
var white:[(Int, Int)] = Array(repeating: (0, 0), count: m)
for i in 0..<n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
black[i] = (line[0], line[1])
}
for i in 0..<m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
white[i] = (line[0], line[1])
}
let blackHul = makeHul(input: black)
let whiteHul = makeHul(input: white)
let p = blackHul.count, q = whiteHul.count
var result = true
for i in blackHul {
if check(a: i, set: whiteHul) {
result = false
break
}
}
for i in whiteHul {
if check(a: i, set: blackHul) {
result = false
break
}
}
loop: for i in 0..<p {
for j in 0..<q {
if !notCrash(a1: blackHul[i], a2: blackHul[(i+1)%p], b1: whiteHul[j], b2: whiteHul[(j+1)%q]) {
result = false
break loop
}
}
}
str += result ? "YES\n" : "NO\n"
}
print(str)