Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "fmt"
- )
- type Building struct {
- left int
- height int
- right int
- }
- func (b Building) ToSkyline() Skyline {
- return Skyline{{b.left, b.height}, {b.right, 0}}
- }
- type Line struct {
- x int
- h int
- }
- type Skyline []Line
- // aの位置で高さ変更するかどうか
- // a, b: 水平線の開始座標, a.x > b.x
- // h: 現在の水平線の高さ
- // 高さ変更する場合水平線の開始座標を返す
- // 変更しない場合はnilを返す
- func check(a Line, b Line, h int) *Line {
- if a.h > b.h || (a.h == b.h && a.h != h) {
- // =と後ろの条件でa, bが同じ高さの場合を考慮
- return &a
- } else if a.h < b.h && b.h != h {
- // 低い場合は引き上げる
- return &Line{a.x, b.h}
- }
- return nil
- }
- func merge(a Skyline, b Skyline) Skyline {
- result := Skyline{}
- h := 0
- i, j := 0, 0
- // 重ならない左側の水平線を追加
- for i < len(a) && a[i].x < b[0].x {
- h = a[i].h
- result = append(result, a[i])
- i++
- }
- for j < len(b) && b[j].x < a[0].x {
- h = b[j].h
- result = append(result, b[j])
- j++
- }
- for i < len(a) && j < len(b) {
- if a[i].x < b[j].x {
- if res := check(a[i], b[j-1], h); res != nil {
- result = append(result, *res)
- h = res.h
- }
- i++
- } else {
- if res := check(b[j], a[i-1], h); res != nil {
- result = append(result, *res)
- h = res.h
- }
- j++
- }
- }
- // 重ならない右側の水平線を追加 (残り)
- for j < len(b) {
- result = append(result, b[j])
- j++
- }
- for i < len(a) {
- result = append(result, a[i])
- i++
- }
- return result
- }
- func resolve(bs []Building) Skyline {
- length := len(bs)
- if length == 1 {
- return bs[0].ToSkyline()
- }
- return merge(resolve(bs[:length/2]), resolve(bs[length/2:]))
- }
- func test_merge(s1 Skyline, s2 Skyline) {
- fmt.Printf("%v\n", merge(s1, s2))
- fmt.Printf("%v\n", merge(s2, s1))
- }
- func test_resolve(bs []Building) {
- fmt.Printf("%v\n", resolve(bs))
- }
- func main() {
- test_merge(Skyline{{1, 2}, {2, 0}}, Skyline{{3, 2}, {4, 0}})
- test_merge(Skyline{{1, 2}, {3, 0}}, Skyline{{2, 3}, {4, 0}})
- test_merge(Skyline{{1, 3}, {3, 0}}, Skyline{{2, 2}, {4, 0}})
- test_merge(Skyline{{1, 3}, {5, 0}}, Skyline{{2, 5}, {3, 3}, {4, 2}, {7, 0}})
- test_merge(Skyline{{2, 4}, {3, 3}, {5, 5}, {7, 2}, {9, 0}}, Skyline{{4, 2}, {5, 1}, {6, 6}, {8, 1}, {11, 0}})
- test_merge(Skyline{{1, 2}, {4, 0}, {8, 2}, {10, 0}}, Skyline{{5, 2}, {7, 0}})
- test_resolve([]Building{{1, 2, 4}, {5, 2, 7}, {8, 2, 10}})
- test_resolve([]Building{{1, 11, 5}, {2, 6, 7}, {3, 13, 9}, {12, 7, 16}, {14, 3, 25}, {19, 18, 22}, {23, 13, 29}, {24, 4, 28}})
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement