Author: Not specified Language: c
Description: Not specified Timestamp: 2018-04-18 20:24:15 +0000
View raw paste Reply
package main

import (
        "bufio"
        "fmt"
        "os"
)

type pt struct {
        x, y int
}

func unique(l []int) []int {
        set := map[int]bool{}
        res := []int{}
        for _, v := range l {
                if !set[v] {
                        set[v] = true
                        res = append(res, v)
                }
        }
        return res
}

func toSet(l []pt) map[pt]bool {
        set := map[pt]bool{}
        for _, v := range l {
                set[v] = true
        }
        return set
}

func solve(r int, zombies []pt) int {
        xs := []int{}
        ys := []int{}
        for _, z := range zombies {
                xs = append(xs, z.x)
                ys = append(ys, z.y)
        }
        xs = unique(xs)
        ys = unique(ys)

        squares := []pt{}
        for _, x := range xs {
                for _, y := range ys {
                        squares = append(squares, pt{x, y})
                }
        }

        zsets := [][]pt{}
        for _, s := range squares {
                set := []pt{}
                for _, z := range zombies {
                        if z.x >= s.x && z.x <= s.x+r && z.y >= s.y && z.y <= s.y+r {
                                set = append(set, z)
                        }
                }
                zsets = append(zsets, set)
        }

        max := 0
        for _, s1 := range zsets {
                for _, s2 := range zsets {
                        size := len(toSet(append(s1, s2...)))
                        if size > max {
                                max = size
                        }
                }
        }
        return max
}

func main() {
        input := bufio.NewReader(os.Stdin)
        var t int
        fmt.Fscanf(input, "%d\n", &t)
        for i := 1; i <= t; i++ {
                var n, r int
                fmt.Fscanf(input, "%d %d\n", &n, &r)
                zombies := make([]pt, n)
                for j := 0; j < n; j++ {
                        fmt.Fscanf(input, "%d %d\n", &zombies[j].x, &zombies[j].y)
                }
                fmt.Printf("Case #%d: %d\n", i, solve(r, zombies))
        }
}
 
View raw paste Reply