【Go言語】AtCoder ABC168 復習(問題E～問題F)

package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
	"strconv"
	"strings"
)

var mod int64 = 1000000007

func modPow2(num int64) int64 {
	if num == 0 {
		return 1
	}

	var rtn int64
	rtn = 1
	var i int64
	for i = 0; i < num; i++ {
		rtn = (rtn << 1) % mod
	}
	return rtn
}

func main() {
	N := getStdinInt64()
	hash1 := make(map[string]int64)
	hash2 := make(map[string]string)
	var zero int64 = 0
	var i int64
	for i = 0; i < N; i++ {
		list := getStdinIntArr64()
		A := list[0]
		B := list[1]
		if A == 0 && B == 0 {
			zero++
		} else if B == 0 {
			hash1["1/0"]++
			hash2["1/0"] = "0/1"
		} else if A == 0 {
			hash1["0/1"]++
			hash2["0/1"] = "1/0"
		} else {
			rat1 := big.NewRat(A, B)
			rat2 := big.NewRat(-B, A)
			hash1[fmt.Sprint(rat1)]++
			hash2[fmt.Sprint(rat1)] = fmt.Sprint(rat2)
		}
	}

	var ans int64 = 1
	for idx, val1 := range hash1 {
		if val1 == -1 {
			continue
		}
		var val2 int64 = hash1[hash2[idx]] // 仲の悪い相方
		var tmp1 int64 = (modPow2(val1) - 1) % mod
		var tmp2 int64 = (modPow2(val2) - 1) % mod
		var tmp3 int64 = 1
		hash1[idx] = -1 // 重複を避ける
		hash1[hash2[idx]] = -1
		ans = (ans * (tmp1 + tmp2 + tmp3)) % mod
	}
	ans = (ans + zero + mod - 1) % mod
	fmt.Printf("%d\n", ans)
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinInt64() int64 {
	sc.Scan()
	rtn, _ := strconv.ParseInt(sc.Text(), 10, 64)
	return rtn
}
func getStdinIntArr64() []int64 {
	sc.Scan()
	str := sc.Text()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

// 線分構造体
type line struct {
	x1, y1   int // 元の位置
	x2, y2   int
	sx1, sy1 int // 圧縮後の位置
	sx2, sy2 int
}

func main() {
	list := getStdinIntArr()
	N := list[0]
	M := list[1]

	lines := make([]line, 0) // 線分
	scalex := make([]int, 0) // idx -> pos
	scaley := make([]int, 0)
	rscalex := make(map[int]int, 0) // pos -> idx
	rscaley := make(map[int]int, 0)
	scalex = append(scalex, 0) // 牛の位置
	scaley = append(scaley, 0)
	// 線分取得
	for i := 0; i < N; i++ {
		list2 := getStdinIntArr()
		A := list2[0]
		B := list2[1]
		C := list2[2]
		lines = append(lines, line{A, C, B, C, 0, 0, 0, 0})
		scalex = append(scalex, A)
		scalex = append(scalex, B)
		scaley = append(scaley, C)
	}
	for i := 0; i < M; i++ {
		list2 := getStdinIntArr()
		D := list2[0]
		E := list2[1]
		F := list2[2]
		lines = append(lines, line{D, E, D, F, 0, 0, 0, 0})
		scalex = append(scalex, D)
		scaley = append(scaley, E)
		scaley = append(scaley, F)
	}
	sort.Ints(scalex)
	sort.Ints(scaley)
	// 検索用に逆ハッシュを持っておく
	for idx, val := range scalex {
		rscalex[val] = idx
	}
	for idx, val := range scaley {
		rscaley[val] = idx
	}
	// 線分情報更新
	for idx, val := range lines {
		lines[idx].sx1 = rscalex[val.x1]
		lines[idx].sx2 = rscalex[val.x2]
		lines[idx].sy1 = rscaley[val.y1]
		lines[idx].sy2 = rscaley[val.y2]
	}

	// 探索用フラグ
	//（線分を入れるために２倍にする）
	mp := make([][]int, len(scaley)*2+1)
	for idx := range mp {
		mp[idx] = make([]int, len(scalex)*2+1)
	}
	// フラグに線分を入れる
	for _, val := range lines {
		if val.sx1 == val.sx2 {
			// 縦線
			x := val.sx1 * 2
			for y := val.sy1 * 2; y <= val.sy2*2; y++ {
				mp[y][x] = -1
			}
		} else {
			// 横線
			y := val.sy1 * 2
			for x := val.sx1 * 2; x <= val.sx2*2; x++ {
				mp[y][x] = -1
			}
		}
	}
	// 面積を入れる
	for y := 0; y < len(scaley)-1; y++ {
		for x := 0; x < len(scalex)-1; x++ {
			mp[y*2+1][x*2+1] = (scalex[x+1] - scalex[x]) * (scaley[y+1] - scaley[y])
		}
	}
	// 幅優先探索で面積を計算する
	parentX := []int{rscalex[0] * 2} // 牛の位置
	parentY := []int{rscaley[0] * 2}
	ans := 0 // 牛の位置の面積
	for {
		pX := parentX[:]
		pY := parentY[:]
		parentX = parentX[len(parentX):]
		parentY = parentY[len(parentY):]

		for idx := range pX {
			x := pX[idx]
			y := pY[idx]

			// 境界チェック
			if x-1 <= 1 || x+1 >= len(mp[0])-1 || y-1 <= 1 || y+1 >= len(mp)-1 {
				fmt.Printf("INF\n")
				return
			}

			// ４方向
			if mp[y-1][x] != -1 {
				if x%2 == 1 && (y-1)%2 == 1 {
					ans += mp[y-1][x]
				}
				parentX = append(parentX, x)
				parentY = append(parentY, y-1)
				mp[y-1][x] = -1
			}
			if mp[y+1][x] != -1 {
				if x%2 == 1 && (y+1)%2 == 1 {
					ans += mp[y+1][x]
				}
				parentX = append(parentX, x)
				parentY = append(parentY, y+1)
				mp[y+1][x] = -1
			}
			if mp[y][x-1] != -1 {
				if (x-1)%2 == 1 && (y)%2 == 1 {
					ans += mp[y][x-1]
				}
				parentX = append(parentX, x-1)
				parentY = append(parentY, y)
				mp[y][x-1] = -1
			}
			if mp[y][x+1] != -1 {
				if (x+1)%2 == 1 && (y)%2 == 1 {
					ans += mp[y][x+1]
				}
				parentX = append(parentX, x+1)
				parentY = append(parentY, y)
				mp[y][x+1] = -1
			}
		}

		if len(parentX) == 0 {
			break
		}
	}

	fmt.Printf("%d\n", ans)
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinIntArr() []int {
	sc.Scan()
	str := sc.Text()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}