fork(1) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class AreaCalculator
  6. {
  7. 	public static void main (String[] args)	{
  8. 		//  _
  9.         // | |_
  10.         // |_ _ |
  11. 		Direction[] input = { Direction.Up, Direction.Up, 
  12. 							  Direction.Right, Direction.Down,
  13. 							  Direction.Right, Direction.Down,
  14. 							  Direction.Left, Direction.Left };
  15.  
  16. 		System.out.println(computeArea(input));
  17.  
  18. 		//  _
  19.         // |_|_
  20.         //   |_|
  21. 		Direction[] input2 = { Direction.Up, Direction.Right, 
  22. 						  	   Direction.Down, Direction.Down,
  23. 							   Direction.Right, Direction.Up,
  24. 							   Direction.Left, Direction.Left };
  25.  
  26. 		System.out.println(computeArea(input2));
  27. 	}
  28.  
  29. 	private static int computeArea(Direction[] directions) {
  30. 		int x = 0, xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
  31. 		int leftmostIndex = 0;
  32. 		for (int i = 0; i < directions.length; i++) {
  33. 			Direction direction = directions[i];
  34. 			x = x + (direction == Direction.Left ? -1 : direction == Direction.Right ? 1 : 0);
  35. 			xMax = x > xMax ? x : xMax;
  36. 			if (x < xMin) {
  37. 				xMin = x;
  38. 				leftmostIndex = (i + 1) % directions.length;
  39. 			}
  40. 		}
  41.  
  42. 		MaxHeap[] heaps = new MaxHeap[xMax - xMin];
  43. 		for (int i = 0; i < heaps.length; i++) heaps[i] = new MaxHeap(4);
  44.  
  45. 		x = 0;
  46. 		int y = 0;
  47. 		int index = leftmostIndex;
  48.  
  49. 		do {
  50. 			Direction direction = directions[index];
  51. 			switch (direction) {
  52. 				case Left: heaps[--x].add(y); break;
  53. 				case Right: heaps[x++].add(y); break;
  54. 				case Up: y++; break;
  55. 				case Down: y--; break;
  56. 			}
  57. 			index = (index + 1) % directions.length;
  58. 		} while (index != leftmostIndex);
  59.  
  60. 		int area = 0;
  61. 		for (MaxHeap heap : heaps) {
  62. 			while (!heap.isEmpty()) {
  63. 				area += heap.popMax() - heap.popMax();
  64. 			}
  65. 		}
  66.  
  67. 		return area;
  68. 	}
  69.  
  70. 	enum Direction {
  71. 		Left,
  72. 		Right,
  73. 		Up,
  74. 		Down
  75. 	}
  76.  
  77. 	private static class MaxHeap {
  78. 		private int[] data;
  79. 		private int size;
  80. 		private int maxSize;
  81.  
  82. 		public MaxHeap(int maxSize) {
  83. 			this.maxSize = maxSize;
  84. 			this.data = new int[maxSize];
  85. 			this.size = 0;
  86. 		}
  87.  
  88. 		public void add(int value) {
  89. 			if (size == maxSize) {
  90. 				int[] oldData = data;
  91. 				maxSize *= 2;
  92. 				data = new int[maxSize];
  93. 				System.arraycopy(oldData, 0, data, 0, size);
  94. 			}
  95.  
  96. 			// bubble up
  97. 			int index = size;
  98. 			while (index > 0  && data[parent(index)] < value) {
  99. 				data[index] = data[parent(index)];
  100. 				index = parent(index);
  101. 			}
  102. 			data[index] = value;
  103.  
  104. 			size++;
  105. 		}
  106.  
  107. 		public int popMax() {
  108. 			assert(size > 0);
  109.  
  110. 			int max = data[0];
  111.  
  112. 			size--;
  113. 			int value = data[size];
  114.  
  115. 			// bubble down
  116. 			int index = 0;
  117. 			int largerChild;
  118. 			while (left(index) < size) {
  119. 				if (right(index) < size) {
  120. 					largerChild = data[left(index)] > data[right(index)]
  121. 									? left(index)
  122. 									: right(index);
  123. 				} else {
  124. 					largerChild = left(index);
  125. 				}
  126.  
  127. 				if (value > data[largerChild]) break;
  128.  
  129. 				data[index] = data[largerChild];
  130. 				index = largerChild;
  131. 			}
  132. 			data[index] = value;
  133.  
  134. 			return max;
  135. 		}
  136.  
  137. 		public boolean isEmpty() {
  138. 			return size == 0;
  139. 		}
  140.  
  141. 		private static int parent(int i) {
  142. 			return (i - 1) / 2;
  143. 		}
  144.  
  145. 		private static int left(int i) {
  146. 			return 2 * i + 1;
  147. 		}
  148.  
  149. 		private static int right(int i) {
  150. 			return 2 * i + 2;
  151. 		}
  152. 	}
  153. }
Success #stdin #stdout 0.1s 320256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
2
https://ideone.com/W2wock
language:
Java (HotSpot 12)
created:
10 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!