백준 10254 고속도로
23 Jun 2021https://www.acmicpc.net/problem/10254
2차원 평면 위에 n개의 도시들이 주어지면 n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾는 문제이다. 컨벡스 헐로 점들을 감쌌을 때 점 사이의 최대 거리는 컨벡스 헐 꼭지점 사이에서만 존재할 수 있다는 개념을 활용한 문제이다.
여기서 로테이팅 캘리퍼스라는 알고리즘이 사용된다. 컨벡스 헐 상의 점들에 대해서 가장 먼 거리는 마치 캘리퍼스를 돌리듯이 확인하는 과정을 통해 쉽게 구할 수 있다는 알고리즘이다. 신기하게도 모든 점들간의 거리를 확인해주면 O(n2)의 시간이 걸리지만 로테이팅 캘리퍼스를 활용하면 O(n)만에 해결이 가능하다.
핵심 아이디어는 임의의 점을 잡았을 때 가장 먼 거리는 임의의 점과 맞다는 상태로 캘리퍼스로 도형을 돌린다고 했을 때 만나게 되는 점들 중에 하나라는 점이다.
위의 그림은 로테이팅 캘리퍼스를 하는 과정 중 일부이다. 실제로 오각형 중 최하단 좌측에 위치한 점으로부터 가장 멀리있는 점의 거리는 첫번째 그림과 두번째 그림의 경우 중 하나에 해당한다. 자세히 보면 최하단 좌측 점은 항상 캘리퍼스 양 끝 선에 맞닿은 채로 확인하고 있다는 것을 알 수 있다.
최종적으로 모든 점들간의 거리를 확인해 줄 필요없이 임의의 점을 기준으로 본인과 가장 멀리있는 점들만 확인하게 된다. 따라서 한 점당 한번씩 방문을 하게되기 때문에 O(n)의 시간이 걸리게 된다.
파일의 입력이 크기때문에 fread를 해줘야 시간초과가 안난다. 관련 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였다. <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>
- 전체 코드
/*
fread 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였습니다.
<출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>
*/
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}
func ccw(a: (Int, Int), b: (Int, Int), c: (Int, Int)) -> Int {
let result:CLongLong = CLongLong(b.0-a.0)*CLongLong(c.1-a.1) - CLongLong(b.1-a.1)*CLongLong(c.0-a.0)
return result > 0 ? 1 : (result == 0 ? 0 : -1)
}
func ccw2(a: (Int, Int), b: (Int, Int), c: (Int, Int), d: (Int, Int)) -> Bool {
let u = (b.0-a.0, b.1-a.1)
let v = (d.0-c.0, d.1-c.1)
return ccw(a: (0, 0), b: u, c: v) >= 0
}
func dist(a: (Int, Int), b: (Int, Int)) -> CLongLong {
let dx = CLongLong(a.0-b.0)
let dy = CLongLong(a.1-b.1)
return dx*dx+dy*dy
}
func convecs(arr: inout [(Int, Int)]) {
var tmp = arr
tmp.sort(by: {$0.1 < $1.1})
tmp.sort(by: {$0.0 < $1.0})
let startP = tmp[0]
tmp[1..<tmp.count].sort(by: {
ccw(a: startP, b: $0, c: $1) == 0 && (dist(a: startP, b: $0) < dist(a: startP, b: $1))
})
tmp[1..<tmp.count].sort(by: {ccw(a: startP, b: $0, c: $1) > 0})
var stack:[(Int, Int)] = []
for i in 0..<tmp.count {
let next = tmp[i]
while stack.count >= 2 && (ccw(a: stack[stack.count-2], b: stack[stack.count-1], c: next) <= 0) {
stack.removeLast()
}
stack.append(next)
}
arr = stack
}
func calipers(arr: [(Int, Int)]) {
let count = arr.count
var pt = 0
var ret:CLongLong = 0
var xx = (0, 0), yy = (0, 0)
for i in 0..<count {
var now:CLongLong = 0
while (pt+1 < count) && ccw2(a: arr[i], b: arr[i+1], c: arr[pt], d: arr[pt+1]) {
now = dist(a: arr[i], b: arr[pt])
if now > ret {
ret = now
xx = arr[i]
yy = arr[pt]
}
pt += 1
}
now = dist(a: arr[i], b: arr[pt])
if now > ret {
ret = now
xx = arr[i]
yy = arr[pt]
}
}
print(xx.0, xx.1, yy.0, yy.1)
}
let fIO = FileIO()
let t = fIO.readInt()
for _ in 0..<t {
let n = fIO.readInt()
var arr:[(Int, Int)] = Array(repeating: (0, 0), count: n)
for i in 0..<n {
arr[i] = (fIO.readInt(), fIO.readInt())
}
convecs(arr: &arr)
calipers(arr: arr)
}