Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.InputStreamReader;
- import java.io.OutputStream;
- import java.io.PrintWriter;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Map;
- import java.util.Queue;
- import java.util.Set;
- import java.util.StringTokenizer;
- public class Main {
- private static class Pair implements Comparable<Pair> {
- private Integer x;
- private Integer y;
- Pair(Integer x, Integer y) {
- this.x = x;
- this.y = y;
- }
- public Integer getX() {
- return x;
- }
- public void setX(Integer x) {
- this.x = x;
- }
- public Integer getY() {
- return y;
- }
- public void setY(Integer y) {
- this.y = y;
- }
- @Override
- public int compareTo(Pair o) {
- if (this.getX() < o.getX()) {
- return -1;
- } else if (this.getX() > o.getX()) {
- return 1;
- } else if (this.getX().equals(o.getX())) {
- if (this.getY() < o.getY()) {
- return -1;
- } else {
- return 1;
- }
- }
- return 0;
- }
- }
- public static void main(String[] args) {
- InputStream inputStream = System.in;
- OutputStream outputStream = System.out;
- InputReader in = new InputReader(inputStream);
- PrintWriter out = new PrintWriter(outputStream);
- Task solver = new Task();
- solver.solve(in, out);
- out.close();
- }
- static class Task {
- private long dist(Pair a, Pair b) {
- return (long)Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
- }
- public void solve(InputReader in, PrintWriter out) {
- int n = in.nextInt();
- HashMap<Integer, Pair> points = new HashMap<>();
- HashMap<Integer, List<Integer>> g = new HashMap<>();
- Map<Integer, Integer> d = new HashMap<>();
- for (int i = 0; i < n; i++) {
- g.put(i, new LinkedList<>());
- d.put(i, 0);
- int x = in.nextInt(), y = in.nextInt();
- points.put(i, new Pair(x, y));
- }
- long k = in.nextLong();
- int start = in.nextInt() - 1, end = in.nextInt() - 1;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- if (dist(points.get(i), points.get(j)) <= k) {
- g.get(i).add(j);
- g.get(j).add(i);
- }
- }
- }
- Queue<Integer> q = new LinkedList<>();
- q.add(start);
- Set<Integer> used = new HashSet<>();
- used.add(start);
- while (!q.isEmpty()) {
- int v = q.poll();
- for (int to : g.get(v)) {
- if (!used.contains(to)) {
- used.add(to);
- q.add(to);
- d.put(to, d.get(v) + 1);
- }
- }
- }
- if (used.contains(end)) {
- out.println(d.get(end));
- } else {
- out.println(-1);
- }
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 2000);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public double nextDouble() {
- return Double.parseDouble(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement