fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4. import java.util.function.*;
  5. import java.text.*;
  6. import static java.lang.Math.*;
  7.  
  8. class Util {
  9. 	static IllegalArgumentException badArgf(String fmt, Object... args) { return new IllegalArgumentException(String.format(fmt, args)); }
  10. 	static RuntimeException impossible() { return impossible(""); }
  11. 	static RuntimeException impossible(String s) { return new RuntimeException(String.format("Внутренняя ошибка%s%s.", s.isEmpty() ? "" : ": ", s)); }
  12. 	static final DecimalFormat humanFloatFormat = new DecimalFormat("#.###");
  13. 	static String humanFloat(double x) { return humanFloatFormat.format(x); }
  14. 	static String trace(Exception e) {
  15. 		StringWriter sw = new StringWriter();
  16. 		e.printStackTrace(new PrintWriter(sw));
  17. 		return sw.toString();
  18. 	}
  19. 	static double sqr(double x) { return x * x; }
  20. }
  21.  
  22. class Vec2 {
  23. 	public final double x, y;
  24. 	public Vec2(double x, double y) { this.x = x; this.y = y; }
  25. 	public static Vec2 Vec2(double x, double y) { return new Vec2(x, y); }
  26. 	public double get(int cid) { if (cid == 0) return x; if (cid == 1) return y; throw badComponentID(cid); }
  27. 	static RuntimeException badComponentID(int cid) { return new IllegalArgumentException(String.format("Неверный индекс компонента Vec2: %d, должен быть 0 или 1.", cid)); }
  28. 	public Vec2 add(Vec2 b) { return Vec2(x + b.x, y + b.y); }
  29. 	public Vec2 sub(Vec2 b) { return Vec2(x - b.x, y - b.y); }
  30. 	public Vec2 mul(Vec2 b) { return Vec2(x * b.x, y * b.y); }
  31. 	public Vec2 mul(double b) { return Vec2(x * b, y * b); }
  32. 	public Vec2 div(Vec2 b) { return Vec2(x / b.x, y / b.y); }
  33. 	public Vec2 div(double b) { return Vec2(x / b, y / b); }
  34. 	@Override public String toString() { return String.format("(%s, %s)", Util.humanFloat(x), Util.humanFloat(y)); }
  35. 	public Vec2 min(Vec2 b) { return Vec2(Math.min(x, b.x), Math.min(y, b.y)); }
  36. 	public Vec2 max(Vec2 b) { return Vec2(Math.max(x, b.x), Math.max(y, b.y)); }
  37. 	public double length() { return sqrt(x*x + y*y); }
  38. 	public double sqrLength() { return x*x + y*y; }
  39. 	public double distanceTo(Vec2 b) { return sub(b).length(); }
  40. 	public double sqrDistanceTo(Vec2 b) { return sub(b).sqrLength(); }
  41. 	// public Vec2 normalized() { return mul(1 / length()); }
  42. }
  43.  
  44. class Segment {
  45. 	// Пересекаются ли отрезки a0–b0 и a1–b1.
  46. 	// https://www. geeksforgeeks.org/check-if-two-given-line-segments-intersect/
  47. 	public static boolean intersects(Vec2 a0, Vec2 b0, Vec2 a1, Vec2 b1) {
  48. 		int o1 = orientation(a0, b0, a1),
  49. 			o2 = orientation(a0, b0, b1),
  50. 			o3 = orientation(a1, b1, a0),
  51. 			o4 = orientation(a1, b1, b0);
  52. 		return o1 != o2 && o3 != o4
  53. 			|| o1 == 0 && onSegment(a0, a1, b0)
  54. 			|| o2 == 0 && onSegment(a0, b1, b0)
  55. 			|| o3 == 0 && onSegment(a1, a0, b1)
  56. 			|| o4 == 0 && onSegment(a1, b0, b1);
  57. 	}
  58.  
  59. 	static double cross0(Vec2 a, Vec2 b, Vec2 c) {
  60. 		return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
  61. 	}
  62.  
  63. 	static int sign(double x) {
  64. 		return x > 0 ? +1 : x < 0 ? -1 : 0;
  65. 	}
  66.  
  67. 	static int orientation(Vec2 a, Vec2 b, Vec2 c) {
  68. 		return sign(cross0(a, b, c));
  69. 	}
  70.  
  71. 	static boolean onSegment1(double a, double x, double b) {
  72. 		return a < b ? x >= a && x <= b : x >= b && x <= a;
  73. 	}
  74.  
  75. 	static boolean onSegment(Vec2 a, Vec2 p, Vec2 b) {
  76. 		return onSegment1(a.x, p.x, b.x) && onSegment1(a.y, p.y, b.y);
  77. 	}
  78. }
  79.  
  80. // Прямоугольник со сторонами, параллельными осям координат. Легко вокруг чего-нибудь описать.
  81. // a — минимальная точка, b — максимальная.
  82. class AABB {
  83. 	public final Vec2 a, b;
  84. 	public AABB(Vec2 a, Vec2 b) { this.a = a; this.b = b; }
  85. 	public static AABB AABB(Vec2 a, Vec2 b) { return new AABB(a, b); }
  86. 	@Override public String toString() { return String.format("A = %s, B = %s", a, b); }
  87.  
  88. 	public static AABB bound(AABB b0, AABB b1) {
  89. 		return AABB(b0.a.min(b1.a), b0.b.max(b1.b));
  90. 	}
  91.  
  92. 	/*public static AABB bound(int count, IntFunction<AABB> ithBB) {
  93. 		if (count <= 0) throw Util.badArgf("AABB.bound: count = %d.", count);
  94. 		var bb = ithBB.apply(0);
  95. 		Vec2 a = bb.a, b = bb.b;
  96. 		for (int i = 1; i < count; i++) {
  97. 			bb = ithBB.apply(i);
  98. 			a = a.min(bb.a);
  99. 			b = b.max(bb.b);
  100. 		}
  101. 		return AABB(a, b);
  102. 	}*/
  103.  
  104. 	public boolean contains(Vec2 p) { return p.x >= a.x && p.x <= b.x && p.y >= a.y && p.y <= b.y; }
  105.  
  106. 	// Остальные 2 точки прямоугольника.
  107. 	public Vec2 bxay() { return Vec2.Vec2(b.x, a.y); }
  108. 	public Vec2 axby() { return Vec2.Vec2(a.x, b.y); }
  109.  
  110. 	public boolean intersectsSegment(Vec2 a, Vec2 b) {
  111. 		Vec2 bxay = this.bxay(), axby = this.axby();
  112. 		return contains(a) || contains(b)
  113. 			// Если ни начало, ни конец отрезка не лежат внутри AABB,
  114. 			// то отрезок, пересекающий AABB, пересекает минимум 2 его стороны,
  115. 			// поэтому на самом деле достаточно проверить какие-нибудь 3, а не все 4.
  116. 			|| Segment.intersects(this.a, axby, a, b)
  117. 			|| Segment.intersects(this.a, bxay, a, b)
  118. 			|| Segment.intersects(axby, this.b, a, b)
  119. 			|| Segment.intersects(bxay, this.b, a, b);
  120. 	}
  121.  
  122. 	public double sqrDistanceTo(Vec2 p) {
  123. 		return p.x < a.x ?
  124. 			p.y < a.y ? p.sqrDistanceTo(a) :
  125. 			p.y > b.y ? p.sqrDistanceTo(axby()) :
  126. 			Util.sqr(a.x - p.x) :
  127. 		p.x > b.x ?
  128. 			p.y < a.y ? p.sqrDistanceTo(bxay()) :
  129. 			p.y > b.y ? p.sqrDistanceTo(b) :
  130. 			Util.sqr(p.x - b.x)
  131. 		:
  132. 			p.y < a.y ? Util.sqr(a.y - p.y) :
  133. 			p.y > b.y ? Util.sqr(p.y - b.y) :
  134. 			0;
  135. 	}
  136. }
  137.  
  138. // Дерево описанных объёмов (bounding volume hierarchy).
  139. // Объекты наследуются от Item, добавляются методом add.
  140. // Дерево перестраивается ВРУЧНУЮ методом rebuild,
  141. // Объекты, пересечённые произвольным отрезком, запрашиваются методом castSegment.
  142. class BVH {
  143. 	public static class Item {
  144. 		public final AABB bb;
  145. 		Item next;
  146. 		Node node;
  147. 		public Item(AABB bb) { this.bb = bb; }
  148. 	}
  149.  
  150. 	// Узлы разбиваются до не более чем MIN_LEAF_NODE_SIZE объектов.
  151. 	// Также узел объединяется с родительским, если после удаления объекта
  152. 	// в нём осталось менее MIN_LEAF_NODE_SIZE объектов.
  153. 	static final int MIN_LEAF_NODE_SIZE = 3;
  154.  
  155. 	// Узел с описанным объёмом bb.
  156. 	// Объекты, пережившие rebuild, содержатся в листовых узлах,
  157. 	// а добавленные с последнего вызова rebuild — в корневом
  158. 	// (так что в запросах будут проверены безусловно).
  159. 	static class Node {
  160. 		AABB bb;
  161. 		BVH bvh;
  162. 		Node left, right, parent;
  163. 		Item first, last;
  164. 		int nItems;
  165.  
  166. 		// Просто добавляет объект в список, не расширяя описанный объём.
  167. 		void addToList(Item item) {
  168. 			if (item.next != null) throw Util.impossible();
  169. 			if (first == null) first = item; else last.next = item;
  170. 			last = item;
  171. 			item.node = this;
  172. 			nItems++;
  173. 		}
  174.  
  175. 		// Добавляет все объекты из списка other.
  176. 		void consumeList(Node other) {
  177. 			if (other.first == null) return;
  178. 			if (first == null) first = other.first; else last.next = other.first;
  179. 			for (Item it = other.first; it != null; it = it.next) it.node = this;
  180. 			last = other.last;
  181. 			other.first = null;
  182. 			other.last = null;
  183. 			nItems += other.nItems;
  184. 			other.nItems = 0;
  185. 		}
  186.  
  187. 		// Сплющивает в node содержимое узла this и его сыновей.
  188. 		void collapseTo(Node node) {
  189. 			if (this != node) node.consumeList(this);
  190. 			if (left != null) { left.collapseTo(node); left = null; }
  191. 			if (right != null) { right.collapseTo(node); right = null; }
  192. 		}
  193.  
  194. 		static AABB bound(AABB b0, AABB b1) {
  195. 			return b0 == null ? b1 : AABB.bound(b0, b1);
  196. 		}
  197.  
  198. 		// Перерассчитывает описанный объём. Если есть дети, то предполагается, что их объёмы уже рассчитаны.
  199. 		void recalculateBB() {
  200. 			AABB bb = null;
  201. 			for (Item it = first; it != null; it = it.next) bb = bound(bb, it.bb);
  202. 			if (left != null) bb = bound(bb, left.bb);
  203. 			if (right != null) bb = bound(bb, right.bb);
  204. 			if (bb == null) throw Util.impossible();
  205. 			this.bb = bb;
  206. 		}
  207.  
  208. 		// Переразбивает node. Предполагается, что он не имеет детей, только объекты
  209. 		// (состояние после collapseTo в самого себя), и что описанный объём рассчитан.
  210. 		void divide() {
  211. 			if (left != null || right != null) throw Util.impossible();
  212. 			// после разбиения в каждом из 2 детей должно остаться MIN_LEAF_NODE_SIZE, так что
  213. 			// 2 * MIN_LEAF_NODE_SIZE — абсолютный минимум.
  214. 			// Но желательно взять больше, чтобы уменьшить шанс выполнить лишнюю работу (см. ниже).
  215. 			if (nItems < 3 * MIN_LEAF_NODE_SIZE) return;
  216. 			// разбиение по максимальному измерению
  217. 			int dim = bb.b.y - bb.a.y > bb.b.x - bb.a.x ? 1 : 0;
  218. 			// в качестве точки разбиения используется среднее арифметическое центров
  219. 			double divp = 0;
  220. 			for (Item it = first; it != null; it = it.next)
  221. 				divp += it.bb.a.get(dim) + it.bb.b.get(dim);
  222. 			divp /= 2 * nItems;
  223.  
  224. 			// разделение на два узла по положению центров относительно divp
  225. 			Node nL = new Node(), nR = new Node();
  226. 			Item next = null;
  227. 			for (Item it = first; it != null; it = next) {
  228. 				next = it.next;
  229. 				it.next = null;
  230. 				if (0.5 * (it.bb.a.get(dim) + it.bb.b.get(dim)) < divp)
  231. 					nL.addToList(it);
  232. 				else
  233. 					nR.addToList(it);
  234. 			}
  235. 			this.nItems = 0;
  236. 			this.first = null;
  237. 			this.last = null;
  238.  
  239. 			// Если всё хорошо, завершить изменения, пересчитать объёмы детей
  240. 			// и рекурсивно продолжить разбиение.
  241. 			if (nL.nItems >= MIN_LEAF_NODE_SIZE && nR.nItems >= MIN_LEAF_NODE_SIZE) {
  242. 				this.left = nL; nL.parent = this; nL.bvh = bvh;
  243. 				this.right = nR; nR.parent = this; nR.bvh = bvh;
  244. 				nL.recalculateBB(); nL.divide();
  245. 				nR.recalculateBB(); nR.divide();
  246. 			} else {
  247. 				// Иначе разбиение выполнено слишком сильно (но кто ж знал),
  248. 				// вернуть объекты из несостоявшихся детей в this.
  249. 				consumeList(nL);
  250. 				consumeList(nR);
  251. 			}
  252. 		}
  253.  
  254. 		// Вызывает cb для объектов, пересекающих отрезок a–b.
  255. 		void castSegment(Vec2 a, Vec2 b, Consumer<Item> cb) {
  256. 			bvh._aabbXsegCalls++;
  257. 			if (!bb.intersectsSegment(a, b)) return;
  258. 			for (Item it = first; it != null; it = it.next) {
  259. 				bvh._aabbXsegCalls++;
  260. 				if (it.bb.intersectsSegment(a, b)) cb.accept(it);
  261. 			}
  262. 			if (left != null) left.castSegment(a, b, cb);
  263. 			if (right != null) right.castSegment(a, b, cb);
  264. 		}
  265. 	}
  266.  
  267. 	Node root;
  268. 	int _aabbXsegCalls, _maxPqSize;
  269.  
  270. 	// add просто добавляет объект в корень, так что он будет проверяться при любых запросах.
  271. 	// Он попадёт в место получше после rebuild.
  272. 	public void add(Item item) {
  273. 		if (item.node != null) throw Util.badArgf("%s уже добавлен.", item);
  274. 		if (root == null) {
  275. 			root = new Node();
  276. 			root.bb = item.bb;
  277. 			root.bvh = this;
  278. 		} else {
  279. 			root.bb = AABB.bound(root.bb, item.bb);
  280. 		}
  281. 		root.addToList(item);
  282. 		item.node = root;
  283. 	}
  284.  
  285. 	public void remove(Item item) {
  286. 		Node node = item.node;
  287. 		if (node == null || node.bvh != this) throw Util.badArgf("%s не %s.", item, node == null ? "добавлен" : "в том дереве");
  288. 		// Удалить item из связного списка, хранящегося в item.node. Можно было бы не искать, если бы он был двусвязным...
  289. 		for (Item it = node.first, prev = null; it != null; prev = it, it = it.next)
  290. 			if (item == it) {
  291. 				if (prev == null) node.first = it; else prev.next = it.next;
  292. 				if (it.next == null) node.last = prev;
  293. 				node.nItems--;
  294. 				item.node = null;
  295. 				break;
  296. 			}
  297. 		if (item.node != null) throw Util.impossible("узел не найден");
  298.  
  299. 		// В листовом узле стало слишком мало объектов? Удалить его, передав оставшиеся объекты родительскому.
  300. 		// Этот процесс может повториться рекурсивно.
  301. 		while (node.nItems < MIN_LEAF_NODE_SIZE && node.left == null && node.right == null) {
  302. 			if (node.parent == null) {
  303. 				if (node.nItems == 0) { node = null; root = null; }
  304. 				break;
  305. 			}
  306. 			node.parent.consumeList(node);
  307. 			if (node == node.parent.left) node.parent.left = null;
  308. 			else if (node == node.parent.right) node.parent.right = null;
  309. 			else throw Util.impossible();
  310. 			node = node.parent;
  311. 		}
  312.  
  313. 		if (node != null) node.recalculateBB();
  314. 	}
  315.  
  316. 	public void rebuild() {
  317. 		if (root == null) return;
  318. 		root.collapseTo(root);
  319. 		root.divide();
  320. 	}
  321.  
  322. 	public void castSegment(Vec2 a, Vec2 b, Consumer<Item> cb) {
  323. 		if (root == null) return;
  324. 		root.castSegment(a, b, cb);
  325. 	}
  326.  
  327. 	public List<Item> castSegment(Vec2 a, Vec2 b) {
  328. 		var r = new ArrayList<Item>();
  329. 		castSegment(a, b, it -> r.add(it));
  330. 		return r;
  331. 	}
  332.  
  333. 	class QueryAroundUnion {
  334. 		boolean isNode;
  335. 		Object obj;
  336. 		double dist;
  337.  
  338. 		public QueryAroundUnion(boolean isNode, Object obj, double dist) {
  339. 			this.isNode = isNode;
  340. 			this.obj = obj;
  341. 			this.dist = dist;
  342. 		}
  343. 		public QueryAroundUnion(Item it, Vec2 p) { this(false, it, it.bb.sqrDistanceTo(p)); }
  344. 		public QueryAroundUnion(Node n, Vec2 p) { this(true, n, n.bb.sqrDistanceTo(p)); }
  345. 	}
  346.  
  347. 	@FunctionalInterface
  348. 	public static interface QueryAroundShoggoth {
  349. 		boolean feed(Item it, double sqrDist);
  350. 	}
  351.  
  352. 	void chopBabies(Node n, PriorityQueue<QueryAroundUnion> q, Vec2 p) {
  353. 		if (n.left != null) q.add(new QueryAroundUnion(n.left, p));
  354. 		if (n.right != null) q.add(new QueryAroundUnion(n.right, p));
  355. 		for (Item it = n.first; it != null; it = it.next) q.add(new QueryAroundUnion(it, p));
  356. 		_maxPqSize = max(_maxPqSize, q.size());
  357. 	}
  358.  
  359. 	public void queryAround(Vec2 p, QueryAroundShoggoth shoggoth) {
  360. 		var q = new PriorityQueue<QueryAroundUnion>(Comparator.comparingDouble(qu -> qu.dist));
  361. 		if (root != null) chopBabies(root, q, p);
  362. 		for (QueryAroundUnion qitem; null != (qitem = q.poll()); )
  363. 			if (qitem.isNode) chopBabies((Node) qitem.obj, q, p);
  364. 			else if (!shoggoth.feed((Item) qitem.obj, qitem.dist)) return;
  365. 	}
  366.  
  367. 	public List<Item> queryAround(Vec2 p) {
  368. 		var r = new ArrayList<Item>();
  369. 		queryAround(p, (it, _sqrDist) -> { r.add(it); return true; });
  370. 		return r;
  371. 	}
  372.  
  373. 	public String dump() {
  374. 		if (root == null) return "<empty>";
  375. 		var sb = new StringBuilder();
  376. 		sb.append("root = {\n");
  377. 		dump(root, sb, 1);
  378. 		sb.append("}");
  379. 		return sb.toString();
  380. 	}
  381.  
  382. 	static StringBuilder tab(StringBuilder sb, int depth) {
  383. 		return sb.append(" ".repeat(2 * depth));
  384. 	}
  385.  
  386. 	static void dump(Node node, StringBuilder sb, int depth) {
  387. 		tab(sb, depth).append(node.bb).append("\n");
  388. 		if (node.nItems != 0) {
  389. 			tab(sb, depth).append("items(").append(node.nItems).append("): ");
  390. 			for (Item it = node.first; it != null; it = it.next) {
  391. 				sb.append(it != node.first ? ", " : "").append(it);
  392. 			}
  393. 			sb.append("\n");
  394. 		}
  395. 		for (int child = 0; child < 2; child++)
  396. 			if ((child == 0 ? node.left : node.right) != null) {
  397. 				tab(sb, depth).append(child == 0 ? "left" : "right").append(" = {\n");
  398. 				dump(child == 0 ? node.left : node.right, sb, depth + 1);
  399. 				tab(sb, depth).append("}\n");
  400. 			}
  401. 	}
  402.  
  403. 	int resetAabbXsegCalls() { int r = _aabbXsegCalls; _aabbXsegCalls = 0; return r; }
  404. 	int resetMaxPqSize() { int r = _maxPqSize; _maxPqSize = 0; return r; }
  405. }
  406.  
  407. class MyItem extends BVH.Item {
  408. 	String name;
  409. 	MyItem(AABB bb, String name) { super(bb); this.name = name; }
  410. 	@Override public String toString() { return name; }
  411. }
  412.  
  413. class Ideone
  414. {
  415. 	static char cyclicLetter(int index) {
  416. 		final int N_LETTERS = (int)'Z' - (int)'A' + 1;
  417. 		return (char) ((int)'A' + (index % N_LETTERS + N_LETTERS) % N_LETTERS);
  418. 	}
  419.  
  420. 	public static void main (String[] args) throws java.lang.Exception
  421. 	{
  422. 		try {
  423. 			var bvh = new BVH();
  424. 			// var toRemove = new ArrayList<MyItem>();
  425. 			for (int y = 0; y < /*10*/ 100; y++) {
  426. 				for (int x = 0; x < /*10*/ 100; x++) {
  427. 					var item = new MyItem(
  428. 						AABB.AABB(
  429. 							Vec2.Vec2(x+0.2, y+0.2),
  430. 							Vec2.Vec2(x+0.8, y+0.8)),
  431. 						"" + cyclicLetter(x) + cyclicLetter(y));
  432. 					// if ((x + y) % 2 < 1) toRemove.add(item);
  433. 					bvh.add(item);
  434. 				}
  435. 			}
  436.  
  437. 			Vec2 segA = Vec2.Vec2(2, 4.3), segB = Vec2.Vec2(7, 3.3);
  438.  
  439. 			System.out.println("1. Запрос на неперестроенном дереве.");
  440. 			System.out.printf("%s\n", bvh.castSegment(segA, segB));
  441. 			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());
  442. 			// String treeDump0 = bvh.dump();
  443.  
  444. 			bvh.rebuild();
  445. 			System.out.println("2. Запрос на перестроенном дереве.");
  446. 			System.out.printf("%s\n", bvh.castSegment(segA, segB));
  447. 			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());
  448. 			// String treeDump1 = bvh.dump();
  449.  
  450. 			/*for (var rem: toRemove) bvh.remove(rem);
  451. 			System.out.printf("3. Запрос после равномерного удаления %d элементов.\n", toRemove.size());
  452. 			System.out.printf("%s\n", bvh.castSegment(segA, segB));
  453. 			System.out.printf("Вызовов AABB.intersectsSegment: %d.\n\n", bvh.resetAabbXsegCalls());*/
  454.  
  455. 			Vec2 epicenter = Vec2.Vec2(7.5, 6.5); // HG
  456. 			/*System.out.printf("3. Сортировка по расстоянию от точки %s.\n", epicenter);
  457. 			bvh.queryAround(epicenter, (it, sqrDist) -> {
  458. 				System.out.printf("%s (%s)\n", it, Util.humanFloat(sqrt(sqrDist)));
  459. 				return true;
  460. 			});
  461. 			System.out.printf("Максимальное число элементов очереди: %d.\n\n", bvh.resetMaxPqSize());*/
  462.  
  463. 			double radius = 3;
  464. 			System.out.printf("3. Сортировка по расстоянию от точки %s, макс. радиус %s.\n", epicenter, Util.humanFloat(radius));
  465. 			bvh.queryAround(epicenter, (it, sqrDist) -> {
  466. 				if (sqrDist > radius * radius) return false;
  467. 				System.out.printf("%s (%s)\n", it, Util.humanFloat(sqrt(sqrDist)));
  468. 				return true;
  469. 			});
  470. 			System.out.printf("Максимальное число элементов очереди: %d.\n\n", bvh.resetMaxPqSize());
  471.  
  472. 			/*System.out.printf("Дамп дерева после шага 1:\n%s\n\n", treeDump0);
  473. 			System.out.printf("Дамп дерева после шага 2:\n%s\n\n", treeDump1);*/
  474. 		} catch (Exception e) {
  475. 			System.out.println(Util.trace(e));
  476. 		}
  477. 	}
  478. }
Success #stdin #stdout 0.22s 52088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1. Запрос на неперестроенном дереве.
[ED, FD, GD, CE]
Вызовов AABB.intersectsSegment: 10001.

2. Запрос на перестроенном дереве.
[CE, ED, FD, GD]
Вызовов AABB.intersectsSegment: 53.

3. Сортировка по расстоянию от точки (7.5, 6.5), макс. радиус 3.
HG (0)
IG (0.7)
HH (0.7)
GG (0.7)
HF (0.7)
IH (0.99)
IF (0.99)
GH (0.99)
GF (0.99)
HI (1.7)
JG (1.7)
HE (1.7)
FG (1.7)
II (1.838)
JH (1.838)
GI (1.838)
JF (1.838)
IE (1.838)
GE (1.838)
FH (1.838)
FF (1.838)
JI (2.404)
JE (2.404)
FI (2.404)
FE (2.404)
KG (2.7)
HJ (2.7)
HD (2.7)
EG (2.7)
IJ (2.789)
GJ (2.789)
KH (2.789)
KF (2.789)
ID (2.789)
GD (2.789)
EH (2.789)
EF (2.789)
Максимальное число элементов очереди: 39.
https://ideone.com/or6C3W
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!