package main import . "fmt" import . "os" import bf "bufio" func main() { rd:=bf.NewReader(Stdin) var n int Fscan(rd,&n) table := make([]int, 4e5+2) for i := 0; i < n; i++ { var x, r int Fscan(rd,&x,&r) x += 2e5 table[x-r]++ table[x+r]-- } // println(Sprint(table[2e5:2e5+20])) var ans, sum int for _, c := range table { sum += c ans = max(ans, sum) } Println(ans) } /* 考察 座標xを-2e5から2e5まで動かして円の個数をカウントする 円の左端(xi-ri)と右端(xi+ri)の座標を見て、左端を過ぎたら円に入り、右端の座標に到達したら円を出る しゃくとり法やいもす法の要領で座標にオフセット+2e5した添え字の配列を使いカウントする、かな 別のやり方では 円の左端と右端の座標だけを入れた配列をソートして この配列を左から走査して左端でインクリメント、右端でデクリメントでカウントしてくでもいいのかな どっちが楽か うーん? 円周は円の内部に含まれないとあるけど サンプルは含んでいるとしないと答えが合わない… 円周の定義を俺が理解していない…? x-rとx+rは円周上だと思ってたけど x-r-1とx+r+1が円周扱いぽくみえる よくわからない よくわからず提出すればWAするかも 案の定WAした 何もわからない サンプルを手計算するか 0 1 2 3 4 5 6 7 8 9 10 11 1) ( * ) 2) ( * ) 3) ( * ) 4) ( * ) 5) ( * ) 6) ( * ) 7) ( * ) 答えの4とは、5 < x < 6 にある… 答えのある位置xは整数だと思い込んでいたのが敗因 サンプルを図示しなかったのも敗因 */