﻿ Fuzhou University OnlineJudge ﻿  Problem 1738 Minimum Distance

## Problem Description

Clustering method requires classifying the point set in space by some way, the inter-set distance in certain class should be sufficient "near."
The general way of clustering is to select a point P, and R as distance measure, as long as the distance between point Q and point P is less than or equal to the distance R, we say that point Q and point P are in a class.
Give you N points in two-dimensional space, and a point P, you should calculate the minimum distance between the N points and the point P. The minimum distance should be not more than the distance R. The distance of Point A(x1,y1) and Point B(x2,y2) is defined as dis(A, B)=| x1-x2 |+| y1-y2 |.

## Input

There are multiple test cases. For each test case, the first line contains two integers N(10≤N≤100,000) and R(1≤R≤100). N is the number of point, the minimum distance should be not more than R. The next N lines, each line contains two integers X and Y(-10000≤X,Y≤10000),(X,Y) indicates a point, these N points are all different.
The next line contains an integer Q(1≤Q≤10000), indicating the number of request. The next Q lines, each line contains two integers Px and Py(-10000≤Px,Py≤10000), indicating we should calculate the minimum distance between the N points and the point P(Px,Py). The minimum distance should be not more than the distance R. The number of points whose distance to point P(Px,Py) is not more than R is not more than 100.

## Output

For each request, output the minimum distance. If the minimum distance does not exist, output “-1”.

## Sample Input

5 1 1 3 2 6 5 3 -1 5 6 5 2 2 3 3 2

1 -1

## Source

FZU 2009 Summer Training Qualification -- Hero Revival 3

Submit  Back  Status  Discuss
﻿ 