Submission #1381153

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int from, to;
	Edge(int f, int t) : from(f), to(t) {}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

vector<int> kosaraju(const Graph& g) {
	int n = g.size(), sz = 0;
	Graph rg(n);
	vector<int>stk, cmp(n, -1), added(n), visited(n), ord(n);
	for (auto &es : g) {
		for (auto &e : es)rg[e.to].emplace_back(e.to, e.from);
		sz += es.size();
	}
	stk.resize(n + sz);
	sz = 0;
	for (int i = 0; i<n; ++i) {
		if (visited[i])continue;
		int s = 0;
		stk[s++] = i;
		while (s != 0) {
			int v = stk[s - 1];
			visited[v] = true;
			bool pushed = false;
			for (auto &e : g[v]) {
				int to = e.to;
				if (!visited[to]) {
					stk[s++] = to;
					pushed = true;
				}
			}
			if (pushed)continue;
			int t = stk[s - 1];
			if (!added[t]) {
				added[t] = true;
				ord[n - ++sz] = t;
			}
			--s;
		}
	}
	int k = 0;
	for (int &u : ord) {
		if (cmp[u] != -1)continue;
		int s = 0;
		stk[s++] = u;
		while (s != 0) {
			int v = stk[--s];
			cmp[v] = k;
			for (auto &e : rg[v]) {
				int t = e.to;
				if (cmp[t] == -1)stk[s++] = t;
			}
		}
		++k;
	}
	return cmp;
}

int main()
{
	int N;
	cin >> N;
	vector<int> x(N), y(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}
	int l = 0, r = 1e9 + 1;
	while (l + 1 < r) {
		int c = l + (r - l) / 2;
		Graph g(N * 2);
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (abs(x[i] - x[j]) < c) {
					g[i].emplace_back(i, N + j);
					g[j].emplace_back(j, N + i);
				}
				if (abs(x[i] - y[j]) < c) {
					g[i].emplace_back(i, j);
					g[N + j].emplace_back(N + j, N + i);
				}
				if (abs(y[i] - x[j]) < c) {
					g[N + i].emplace_back(N + i, N + j);
					g[j].emplace_back(j, i);
				}
				if (abs(y[i] - y[j]) < c) {
					g[N + i].emplace_back(N + i, j);
					g[N + j].emplace_back(N + j, i);
				}
			}
		}
		auto v = kosaraju(g);
		bool can = true;
		for (int i = 0; i < N; i++) {
			if (v[i] == v[i + N]) {
				can = false;
			}
		}
		if (can) {
			l = c;
		}
		else {
			r = c;
		}
	}
	cout << l << endl;
	return 0;
}

Submission Info

Judge Result