题目详情题解（0）讨论（0）提交记录（0）

AT_abc366_e.[ABC366E] Manhattan Multifocal Ellipse

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

二维平面上有 NN 个点 (x1,y1),(x2,y2),…,(xn,yn)(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)，给你一个正整数 DD，求有多少组整数对 (x,y)(x,y) 满足

∑i=1N(∣x−xi∣+∣y−yi∣)≤D\sum\limits^N_{i=1}(|x-x_i|+|y-y_i|) \leq D

输入格式

第一行两个正整数 N,DN,D。接下来 NN 行，每行两个整数，表示二维平面上点的坐标。

输出格式

一行一个整数，表示你的答案。

输入输出样例

  • 输入#1

    2 3
0 0
1 0

    输出#1

    8

  • 输入#2

    2 0
0 0
2 0

    输出#2

    0

  • 输入#3

    6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

    输出#3

    419

说明/提示

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5

  • 0≤D≤1060 \leq D \leq 10^6

  • −106≤xi,yi≤106-10^6 \leq x_i,y_i \leq 10^6

  • 保证对于所有的 i≠ji \ne j，(xi,yi)≠(xj,yj)(x_i,y_i) \ne (x_j,y_j)。

  • 所有输入均为整数。

输入解题思路，AI测评打分。不知道怎么写?

首页