F. Rain of Fire SOLUTIONS CODEFORCES

Rain of Fire SOLUTIONS CODEFORCES

There are nn detachments on the surface, numbered from 11 to nn, the ii-th detachment is placed in a point with coordinates (xi,yi)(xi,yi). All detachments are placed in different points.

Brimstone should visit each detachment at least once. You can choose the detachment where Brimstone starts.

To move from one detachment to another he should first choose one of four directions of movement (up, right, left or down) and then start moving with the constant speed of one unit interval in a second until he comes to a detachment. After he reaches an arbitrary detachment, he can repeat the same process.

Each tt seconds an orbital strike covers the whole surface, so at that moment Brimstone should be in a point where some detachment is located. He can stay with any detachment as long as needed.

Brimstone is a good commander, that’s why he can create at most one detachment and place it in any empty point with integer coordinates he wants before his trip. Keep in mind that Brimstone will need to visit this detachment, too.

Help Brimstone and find such minimal tt that it is possible to check each detachment. If there is no such tt report about it.Input

The first line contains a single integer nn (2≤n≤1000)(2≤n≤1000) — the number of detachments.

In each of the next nn lines there is a pair of integers xixi, yiyi (|xi|,|yi|≤109)(|xi|,|yi|≤109) — the coordinates of ii-th detachment.

It is guaranteed that all points are different.Output

Output such minimal integer tt that it is possible to check all the detachments adding at most one new detachment.

If there is no such tt, print −1−1.

Examples

input

4
100 0
0 100
-100 0
0 -100

output

100

input

7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

output

-1

input

5
0 0
0 -1
3 0
-2 0
-2 1

output

2

input

5
0 0
2 0
0 -1
-2 0
-2 1

output

2

Note

In the first test it is possible to place a detachment in (0,0)(0,0), so that it is possible to check all the detachments for t=100t=100. It can be proven that it is impossible to check all detachments for t<100t<100; thus the answer is 100100.

In the second test, there is no such tt that it is possible to check all detachments, even with adding at most one new detachment, so the answer is −1−1.

In the third test, it is possible to place a detachment in (1,0)(1,0), so that Brimstone can check all the detachments for t=2t=2. It can be proven that it is the minimal such tt.

In the fourth test, there is no need to add any detachments, because the answer will not get better (t=2t=2). It can be proven that it is the minimal such tt.

Solution:

Program C++:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int INF = 2020202020;

int N;
int X[1010];
int Y[1010];

vector<pii> V[1010];
vector<pii> H[1010];

vector<int> xs, ys;
bool chk[1010];

struct DSU {
	int p[1010];
	int n, com;

	void init(int _n) {
		n = com = _n;
		for(int i = 1; i <= n; i++) p[i] = i;
	}

	int par(int x) {
		if(x == p[x]) return x;
		return p[x] = par(p[x]);
	}

	void unite(int a, int b) {
		a = par(a); b = par(b);
		if(a == b) return;
		p[a] = b;
		com--;
	}
	
	int count() {
		return com;
	}
}uf;

void comv(vector<int>& v) {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
}

int get_idx(vector<int>& v, int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

bool solve(int dst) {
	// printf("dst = %d\n", dst);
	uf.init(N);

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j < H[i].size(); j++) {
			if(H[i][j].first - H[i][j - 1].first <= dst) uf.unite(H[i][j - 1].second, H[i][j].second);
		}
		for(int j = 1; j < V[i].size(); j++) {
			if(V[i][j].first - V[i][j - 1].first <= dst) uf.unite(V[i][j - 1].second, V[i][j].second);
		}
	}

	int c = uf.count();
	if(c > 4) return false;
	if(c == 1) return true;

	auto f = [&](int x, int y) {
		int u = 0, d = 0, l = 0, r = 0;
		auto it = lower_bound(xs.begin(), xs.end(), x);
		if(*it == x) {
			int xi = it - xs.begin() + 1;
			auto it2 = lower_bound(V[xi].begin(), V[xi].end(), pii(y, 0));
			if(it2 != V[xi].end()) u = it2 -> second;
			if(it2 != V[xi].begin()) d = (--it2) -> second;
		}

		it = lower_bound(ys.begin(), ys.end(), y);
		if(*it == y) {
			int yi = it - ys.begin() + 1;
			auto it2 = lower_bound(H[yi].begin(), H[yi].end(), pii(x, 0));
			if(it2 != H[yi].end()) r = it2 -> second;
			if(it2 != H[yi].begin()) l = (--it2) -> second;
		}

		if(u && Y[u] - y > dst) u = 0;
		if(d && y - Y[d] > dst) d = 0;
		if(r && X[r] - x > dst) r = 0;
		if(l && x - X[l] > dst) l = 0;

		if(u) u = uf.par(u);
		if(d) d = uf.par(d);
		if(r) r = uf.par(r);
		if(l) l = uf.par(l);

		set<int> S;
		for(int i : {u, d, r, l}) {
			if(i) S.insert(i);
		}
		if(S.size() >= c) return true;
		return false;
	};

	for(int i = 0; i < xs.size(); i++) {
		for(int j = 0; j < ys.size(); j++) {
			if(f(xs[i], ys[j])) return true;
		}
	}

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j < H[i].size(); j++) {
			int x1 = H[i][j - 1].first, x2 = H[i][j].first;
			if(x2 - x1 <= dst || x2 - x1 > 2 * dst) continue;
			int y = ys[i - 1], x = (x1 + x2) / 2;
			if(f(x, y)) return true;
		}
		for(int j = 1; j < V[i].size(); j++) {
			int y1 = V[i][j - 1].first, y2 = V[i][j].first;
			if(y2 - y1 <= dst || y2 - y1 > 2 * dst) continue;
			int x = xs[i - 1], y = (y1 + y2) / 2;
			if(f(x, y)) return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%d%d", &X[i], &Y[i]);
		xs.push_back(X[i]);
		ys.push_back(Y[i]);
	}

	comv(xs); comv(ys);

	for(int i = 1; i <= N; i++) {
		H[get_idx(ys, Y[i])].emplace_back(X[i], i);
		V[get_idx(xs, X[i])].emplace_back(Y[i], i);
	}

	for(int i = 1; i <= N; i++) {
		sort(H[i].begin(), H[i].end());
		sort(V[i].begin(), V[i].end());
	}

	int l = 1, r = INF;
	while(l <= r) {
		ll m = (ll)l + r >> 1;
		if(solve(m)) r = m - 1;
		else l = m + 1;
	}
	printf("%d\n", l > INF ? -1 : l);

	return 0;
}

Program Java:

import java.io.*;
import java.util.*;
 
public class Solution extends PrintWriter {

    long MX = 1000000000L;
    
    private void solve() {
        n = sc.nextInt();
        p = new long[n][];
        for(int i = 0; i < n; i++) {
            p[i] = new long[] {2L*sc.nextLong(), 2L*sc.nextLong(), i, 0L, 0L};
        }

        adj = new ArrayDeque[n];
        for(int i = 0; i < n; i++) adj[i] = new ArrayDeque<>();
        
        points_by = new Integer[2][][];
        axis = new Long[2][];
        for(int i = 0; i < 2; i++) {
            axis[1-i] = axis(i);
        }
        
        for(int i = 0; i < 2; i++) {
            compressed(i);
        }
        
        
        Arrays.sort(p, Comparator.comparing(arr -> arr[2]));

        comp = new int[n];
        done = new boolean[n];
        
        verify(2L*810517601L);
        
        long l = -1;
        long r = 1L;
        
        while(!verify(r)) {
            r = 2L*r;
            if(r > 8*MX) {
                println(-1);
                return;
            }
        }
        
        while(l < r-1) {
            long mid = (l+r)/2L;
            if(!verify(mid)) l = mid;
            else r = mid;
        }
        println((r+1L)/2L);
    }
    
    void compressed(int ax) {
        Arrays.sort(axis[ax]);
        Arrays.sort(p, Comparator.comparing((long[] arr) -> arr[ax]));
        for(int i = 0, j = 0; i < axis[ax].length; i++) {
            while(j < p.length && p[j][ax] == axis[ax][i]) {
                p[j][3+ax] = i;
                j++;
            }
        }
    }
    
    ArrayDeque<long[]>[] adj;
    
    int n;
    long[][] p;
    
    Long[][] axis;
    
    Integer[][][] points_by;
    
    Long[] axis(int ax) {
        Arrays.sort(p, Comparator.comparing((long[] arr) -> arr[ax]).thenComparing(arr -> arr[1-ax]));
        ArrayList<Long> _y = new ArrayList<>();
        ArrayList<Integer[]> _points_by = new ArrayList<>();
        for(int i = 0, j; i < n; i = j) {
            for(j = i; j < n && p[i][ax] == p[j][ax]; j++);
            Integer[] __points_by = new Integer[j-i];
            for(int k = i; k < j; k++) {
                _y.add(p[k][1-ax]);
                __points_by[k-i] = (int)p[k][2];
                if(k >= j-1) break;
                _y.add((p[k][1-ax] +p[k+1][1-ax])/2L); 
                int u = (int) p[k][2];
                int v = (int) p[k+1][2];
                long cost = p[k+1][1-ax]-p[k][1-ax];
                adj[u].add(new long[] {v, cost});
                adj[v].add(new long[] {u, cost});
            }
            _points_by.add(__points_by);
        }
        points_by[ax] = _points_by.toArray(new Integer[0][]);
        return _y.toArray(new Long[0]);
    }
    
    boolean verify(long t) {
        Arrays.fill(comp, 0);
        Arrays.fill(done, false);
        comp_sz = 0;
        for(int u = 0; u < n; u++) {
            if(!done[u]) {
                dfs(u, t);
                comp_sz++;
            }            
        }
        if(comp_sz == 1) return true;
        if(comp_sz <= 4) {
            if(doit_(t, 0)) return true;
            if(doit_(t, 1)) return true;
        }
        return false;
    }
    
    boolean doit_(long t, int ax) {
        int other_ax = 1-ax;
        for(int i = 0; i < points_by[other_ax].length; i++) {
            int y = (int) p[points_by[other_ax][i][0]][other_ax];
            boolean[][] covered = new boolean[comp_sz][axis[ax].length];
            int[] idx_axis = new int[comp_sz];
            for(int j = 0; j < points_by[other_ax][i].length; j++) {
                int idx = points_by[other_ax][i][j];
                long l = p[idx][ax]-t;
                long r = p[idx][ax]+t;
                while(idx_axis[comp[idx]] < axis[ax].length && axis[ax][idx_axis[comp[idx]]] <= r) {
                    if(axis[ax][idx_axis[comp[idx]]] >= l) {
                        covered[comp[idx]][idx_axis[comp[idx]]] = true;
                    }
                    idx_axis[comp[idx]]++;
                }
            }
            for(int k = 0; k < points_by[other_ax].length; k++) {
                if(Math.abs(p[points_by[other_ax][k][0]][other_ax]-y) > t) continue;
                if(k != i) {
                    for(int j = 0; j < points_by[other_ax][k].length; j++) {
                        int idx = points_by[other_ax][k][j];
                        covered[comp[idx]][(int) p[idx][3+ax]] = true;
                    }
                }
            }
            for(int j = 0; j < axis[ax].length; j++) {
                boolean ok = true;
                for(int k = 0; k < comp_sz; k++) {
                    if(!covered[k][j]) {
                        ok = false;
                        break;
                    }                    
                }
                if(ok) return true;
            }
        }
        return false;
    }
    
    int[] comp;
    boolean[] done;
    int comp_sz;
    
    void dfs(int u, long t) {
        done[u] = true;
        comp[u] = comp_sz;
        for(long[] vv : adj[u]) {
            int v = (int) vv[0];
            if(!done[v] && vv[1] <= t) {
                dfs(v, t);
            }
        }
    }
    

//  Solution() throws FileNotFoundException { super(new File("output.txt")); }
//  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
  Solution() { super(System.out); }
  InputReader sc = new InputReader(System.in);
  static class InputReader {
      InputReader(InputStream in) { this.in = in; } InputStream in;
      
      private byte[] buf = new byte[16384];
      private int    curChar;
      private int    numChars;
      
 
      public int read() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = in.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextLine() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isEndOfLine(c));
          return res.toString();
      }
 
      public String nextString() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isSpaceChar(c));
          return res.toString();
      }
 
      public long nextLong() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          long res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public int nextInt() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      private boolean isSpaceChar(int c) {
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      private boolean isEndOfLine(int c) {
          return c == '\n' || c == '\r' || c == -1;
      }
  }
 
    public static void main(String[] $) {
        new Thread(null, new Runnable() {
            public void run() {
                long start = System.nanoTime();
                try {Solution solution = new Solution(); solution.solve(); solution.flush();} 
                catch (Exception e) {e.printStackTrace(); System.exit(1);}
                System.err.println((System.nanoTime()-start)/1E9);
            }
        }, "1", 1 << 27).start();
 
    }
    

}

Program Python:

import math
def eratosphen():
    n = 10**5
    a = [i for i in range(n + 1)]

    a[1] = 0
    lst = []

    i = 2
    while i <= n:
        if a[i] != 0:
            lst.append(a[i])
            for j in range(i, n + 1, i):
                a[j] = 0
        i += 1
    return lst

def main():
    erat = eratosphen()
    erat = set(erat)
    t = int(input())

    while t > 0:
        div = dict()
        n = int(input())
        for i in range(2, int(math.sqrt(n))+ 2):
            if n % i == 0 and i in erat:
                div[i] = [1]
                while n % i == 0:
                    n //= i
                    div[i].append(div[i][-1]*i)
        nums = sorted(div.keys())
        line = ""
        last_value = 0
        tot_values = []
        for i in range(0, len(nums)):
            values = div[nums[i]][1:]

            for k in range(i + 1, len(nums)):
                ln = len(values)
                for m in range(ln):
                    for r in range(1, len(div[nums[k]])):
                        if i != len(nums) - 1 and values[m]*div[nums[k]][r] != nums[i]*nums[i + 1]:
                            values.append(values[m]*div[nums[k]][r])
            if i == 0:
                tot_values.append(values[-1])
                values.pop()
            for r in values:
                tot_values.append(r)
            if i != len(nums) - 1:
                tot_values.append(nums[i]*nums[i + 1])

        line = ""
        for i in range(len(tot_values)):
            line += str(tot_values[i]) + " "
        print(line)
        if len(tot_values) == 3:
            print("1")

        else:
            print("0")
        t -= 1

if __name__ == '__main__':

    t = 1
    for i in range(t):
        main()

Related : 

Leave a Comment