fork download
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. #define SZ(x) ((int)x.size())
  8. #define ALL(V) V.begin(), V.end()
  9. #define L_B lower_bound
  10. #define U_B upper_bound
  11. #define pb push_back
  12.  
  13. #define FOR(i, a, b) for (int i=a; i<(b); i++)
  14. #define F0R(i, a) for (int i=0; i<(a); i++)
  15. #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
  16. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  17.  
  18. using namespace std;
  19. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  20. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  21. const int MAXN = (int)1e5 + 42;
  22.  
  23. /// Benq 2-Sat and scc
  24. template<int SZ> struct scc {
  25. vector<int> adj[SZ], radj[SZ], todo, allComp;
  26. int N, comp[SZ];
  27. bitset<SZ> visit;
  28.  
  29. void clear(int n)
  30. {
  31. for(int i = 0; i < n; i++)
  32. adj[i].clear(), radj[i].clear();
  33. allComp.clear();
  34. todo.clear();
  35. }
  36.  
  37. void clear_2()
  38. {
  39. allComp.clear();
  40. todo.clear();
  41. }
  42.  
  43. void dfs(int v) {
  44. visit[v] = 1;
  45. for (int w: adj[v]) if (!visit[w]) dfs(w);
  46. todo.pb(v);
  47. }
  48.  
  49. void dfs2(int v, int val) {
  50. comp[v] = val;
  51. for (int w: radj[v]) if (comp[w] == -1) dfs2(w,val);
  52. }
  53.  
  54. void addEdge(int a, int b) { adj[a].pb(b), radj[b].pb(a); }
  55.  
  56. void genSCC() {
  57. F0R(i,N) comp[i] = -1, visit[i] = 0;
  58. F0R(i,N) if (!visit[i]) dfs(i);
  59. reverse(ALL(todo)); // toposort
  60. for (int i: todo) if (comp[i] == -1) dfs2(i,i), allComp.pb(i);
  61. }
  62. };
  63.  
  64. template<int SZ> struct twosat {
  65. scc<2*SZ> S;
  66. int N;
  67.  
  68. void SetTrue(int x) { S.addEdge(x^1,x); }
  69.  
  70. void NotBoth1(int x, int y)
  71. {
  72. S.addEdge(x, y^1);
  73. S.addEdge(y, x^1);
  74. }
  75.  
  76. void SetBothSame(int x, int y)
  77. {
  78. //cout << "SAME" << x / 2 << " " << y / 2 << endl;
  79.  
  80. S.addEdge(x, y);
  81. S.addEdge(y, x);
  82.  
  83. S.addEdge(x ^ 1, y ^ 1);
  84. S.addEdge(y ^ 1, x ^ 1);
  85. }
  86.  
  87. int tmp[2*SZ];
  88. bitset<SZ> ans;
  89.  
  90. void init(int n)
  91. {
  92. S.clear(2 * n);
  93. N = n;
  94. for(int i = 0; i < SZ; i++)
  95. tmp[2 * i] = tmp[2 * i + 1] = 0, ans[i] = 0;
  96. }
  97.  
  98. void clear_sat()
  99. {
  100. S.clear_2();
  101. for(int i = 0; i < SZ; i++)
  102. tmp[2 * i] = tmp[2 * i + 1] = 0, ans[i] = 0;
  103. }
  104.  
  105. bool solve() {
  106. S.N = 2*N; S.genSCC();
  107. for (int i = 0; i < 2*N; i += 2) if (S.comp[i] == S.comp[i^1]) return 0;
  108. reverse(ALL(S.allComp));
  109. for (int i: S.allComp) if (tmp[i] == 0)
  110. tmp[i] = 1, tmp[S.comp[i^1]] = -1;
  111. F0R(i,N) if (tmp[S.comp[2*i]] == 1) ans[i] = 1;
  112. return 1;
  113. }
  114. };
  115.  
  116. int n, X[MAXN], Y[MAXN];
  117. map<int, vector<pair<int, int> > > on_x;
  118. map<int, vector<pair<int, int> > > on_y;
  119. vector<pair<pair<int, int>, int> > Vec;
  120.  
  121. int read_int();
  122.  
  123. void read()
  124. {
  125. n = read_int();
  126. for(int i = 0; i < n; i++)
  127. {
  128. int x, y;
  129. x = read_int();
  130. y = read_int();
  131.  
  132. X[i] = x;
  133. Y[i] = y;
  134.  
  135. on_x[x].push_back({y, i});
  136. on_y[y].push_back({x, i});
  137. Vec.push_back({{x, y}, i});
  138. }
  139. }
  140.  
  141. twosat<MAXN> sat2;
  142. set<pair<int, int> > st;
  143.  
  144. bool simple_check(int64_t d)
  145. {
  146. sat2.init(n);
  147.  
  148. for(auto X: on_x)
  149. {
  150. // currently looking at |
  151.  
  152. int last = -2 * d - 42, il = -1;
  153. for(auto it: X.second)
  154. {
  155. if((int64_t)it.first - last <= d)
  156. {
  157. sat2.SetTrue(it.second * 2);
  158. sat2.SetTrue(il * 2);
  159. }
  160. else if((int64_t)it.first - last <= 2 * d)
  161. sat2.NotBoth1(it.second * 2 + 1, il * 2 + 1);
  162.  
  163. last = it.first;
  164. il = it.second;
  165. }
  166. }
  167.  
  168. for(auto X: on_y)
  169. {
  170. // currently looking at -
  171.  
  172. int last = -2 * d - 42, il = -1;
  173. for(auto it: X.second)
  174. {
  175. if((int64_t)it.first - last <= d)
  176. {
  177. sat2.SetTrue(it.second * 2 + 1);
  178. sat2.SetTrue(il * 2 + 1);
  179. }
  180. else if((int64_t)it.first - last <= 2 * d)
  181. sat2.NotBoth1(it.second * 2, il * 2);
  182.  
  183. last = it.first;
  184. il = it.second;
  185. }
  186. }
  187.  
  188. return sat2.solve();
  189. }
  190.  
  191. bool check(int d)
  192. {
  193. if(!simple_check(d)) return false;
  194.  
  195. sat2.clear_sat();
  196.  
  197. int p_l = 0;
  198. st.clear();
  199. for(int i = 0; i < n; i++)
  200. {
  201. while(Vec[i].first.first - Vec[p_l].first.first > d) st.erase({Vec[p_l].first.second, Vec[p_l].second}), p_l++;
  202.  
  203. int y = Vec[i].first.second, idx = Vec[i].second;
  204.  
  205. auto R = st.lower_bound({y, MAXN});
  206. if(R != st.end() && R->first - y <= d)
  207. sat2.SetBothSame(R->second * 2, idx * 2);
  208.  
  209. if(R != st.begin())
  210. {
  211. R--;
  212. if(y - R->first <= d)
  213. sat2.SetBothSame(R->second * 2, idx * 2);
  214. }
  215.  
  216. if(i != n - 1 && Vec[i].first.first != Vec[i + 1].first.first)
  217. {
  218. if(Vec[i + 1].first.first - Vec[i].first.first > d) st.clear(), p_l = i + 1;
  219. else for(int j = i; j >= 0 && Vec[j].first.first == Vec[i].first.first; j--)
  220. st.insert({Vec[j].first.second, Vec[j].second});
  221. }
  222. }
  223.  
  224. return sat2.solve();
  225. }
  226.  
  227. void solve()
  228. {
  229. for(auto &it: on_x)
  230. sort(ALL(it.second));
  231. for(auto &it: on_y)
  232. sort(ALL(it.second));
  233.  
  234. sort(ALL(Vec));
  235.  
  236. if(check((int)1e9 + 42))
  237. {
  238. cout << -1 << endl;
  239. for(int i = 0; i < n; i++)
  240. cout << (sat2.ans[i] ? '-' : '|');
  241. return;
  242. }
  243.  
  244. int low = 0, high = (int)1e9, mid, ret = 0;
  245.  
  246. /*for(int i = 0; high - (1 << i) >= low; i++)
  247. if(!check(high - (1 << i))) high -= (1 << i);
  248. else
  249. {
  250. ret = high - (1 << i);
  251. low = high - (1 << i) + 1;
  252. break;
  253. }*/
  254.  
  255. for(int i = 0; i < n; i++)
  256. {
  257. int vert = (int)1e9, hor = (int)1e9;
  258.  
  259. {
  260. auto &V = on_x[X[i]];
  261.  
  262. auto L = U_B(ALL(V), make_pair(Y[i], i)) - V.begin();
  263. if(L != SZ(V))
  264. chkmin(vert, V[L].first - Y[i]);
  265.  
  266. L -= 2;
  267. if(L >= 0)
  268. chkmin(vert, Y[i] - V[L].first);
  269. }
  270.  
  271. {
  272. auto &V = on_y[Y[i]];
  273.  
  274. auto L = U_B(ALL(V), make_pair(X[i], i)) - V.begin();
  275. if(L != SZ(V))
  276. chkmin(hor, V[L].first - X[i]);
  277.  
  278. L -= 2;
  279. if(L >= 0)
  280. chkmin(hor, X[i] - V[L].first);
  281. }
  282.  
  283. chkmin(high, max(hor, vert));
  284. }
  285.  
  286. while(low <= high)
  287. {
  288. mid = (low + high) >> 1;
  289. if(check(mid))
  290. ret = mid, low = mid + 1;
  291. else
  292. high = mid - 1;
  293. }
  294.  
  295. check(ret);
  296. cout << ret << endl;
  297. for(int i = 0; i < n; i++)
  298. cout << (sat2.ans[i] ? '-' : '|');
  299. }
  300.  
  301. int main()
  302. {
  303. ios_base::sync_with_stdio(false);
  304. cin.tie(NULL);
  305.  
  306. read();
  307. solve();
  308. return 0;
  309. }
  310.  
  311. const int maxl = 100000;
  312. char buff[maxl];
  313. int ret_int, pos_buff = 0;
  314.  
  315. void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0; }
  316.  
  317. int read_int()
  318. {
  319. ret_int = 0;
  320. for(; buff[pos_buff] < '0' || buff[pos_buff] > '9'; next_char());
  321. for(; buff[pos_buff] >= '0' && buff[pos_buff] <= '9'; next_char())
  322. ret_int = ret_int * 10 + buff[pos_buff] - '0';
  323. return ret_int;
  324. }
Time limit exceeded #stdin #stdout 5s 27112KB
stdin
Standard input is empty
stdout
Standard output is empty