Author: Not specified Language: c
Description: Not specified Timestamp: 2018-04-18 20:24:05 +0000
View raw paste Reply
  1. package main
  2.  
  3. import (
  4.         "bufio"
  5.         "fmt"
  6.         "os"
  7. )
  8.  
  9. type pt struct {
  10.         x, y int
  11. }
  12.  
  13. func unique(l []int) []int {
  14.         set := map[int]bool{}
  15.         res := []int{}
  16.         for _, v := range l {
  17.                 if !set[v] {
  18.                         set[v] = true
  19.                         res = append(res, v)
  20.                 }
  21.         }
  22.         return res
  23. }
  24.  
  25. func toSet(l []pt) map[pt]bool {
  26.         set := map[pt]bool{}
  27.         for _, v := range l {
  28.                 set[v] = true
  29.         }
  30.         return set
  31. }
  32.  
  33. func solve(r int, zombies []pt) int {
  34.         xs := []int{}
  35.         ys := []int{}
  36.         for _, z := range zombies {
  37.                 xs = append(xs, z.x)
  38.                 ys = append(ys, z.y)
  39.         }
  40.         xs = unique(xs)
  41.         ys = unique(ys)
  42.  
  43.         squares := []pt{}
  44.         for _, x := range xs {
  45.                 for _, y := range ys {
  46.                         squares = append(squares, pt{x, y})
  47.                 }
  48.         }
  49.  
  50.         zsets := [][]pt{}
  51.         for _, s := range squares {
  52.                 set := []pt{}
  53.                 for _, z := range zombies {
  54.                         if z.x >= s.x && z.x <= s.x+r && z.y >= s.y && z.y <= s.y+r {
  55.                                 set = append(set, z)
  56.                         }
  57.                 }
  58.                 zsets = append(zsets, set)
  59.         }
  60.  
  61.         max := 0
  62.         for _, s1 := range zsets {
  63.                 for _, s2 := range zsets {
  64.                         size := len(toSet(append(s1, s2...)))
  65.                         if size > max {
  66.                                 max = size
  67.                         }
  68.                 }
  69.         }
  70.         return max
  71. }
  72.  
  73. func main() {
  74.         input := bufio.NewReader(os.Stdin)
  75.         var t int
  76.         fmt.Fscanf(input, "%d\n", &t)
  77.         for i := 1; i <= t; i++ {
  78.                 var n, r int
  79.                 fmt.Fscanf(input, "%d %d\n", &n, &r)
  80.                 zombies := make([]pt, n)
  81.                 for j := 0; j < n; j++ {
  82.                         fmt.Fscanf(input, "%d %d\n", &zombies[j].x, &zombies[j].y)
  83.                 }
  84.                 fmt.Printf("Case #%d: %d\n", i, solve(r, zombies))
  85.         }
  86. }
  87.  
View raw paste Reply