fork download
copy 
  1. public class BichromeSky
  2. {
  3. 	class Point
  4. 	{
  5. 		double x, y;
  6.  
  7. 		Point(double _x, double _y)
  8. 		{
  9. 			x = _x;
  10. 			y = _y;
  11. 		}
  12.  
  13. 		Point to(Point t)
  14. 		{
  15. 			return new Point(t.x - x, t.y - y);
  16. 		}
  17.  
  18. 		double crossProduct(Point t)
  19. 		{
  20. 			return x * t.y - y * t.x;
  21. 		}
  22.  
  23. 		double direction()
  24. 		{
  25. 			return Math.atan2(y, x);
  26. 		}
  27. 	}
  28.  
  29. 	class Range
  30. 	{
  31. 		double from;
  32. 		double to;
  33. 		double prob;
  34. 	}
  35.  
  36. 	double fix(double ang)
  37. 	{
  38. 		ang = ang * 180 / Math.PI;
  39. 		while(ang < 0) ang += 360;
  40. 		while(ang >= 360) ang -= 360;
  41. 		return ang;
  42. 	}
  43.  
  44. 	Range coverRange(Point[] points, Point p)
  45. 	{
  46. 		Range ret = new Range();
  47. 		for(int i = 0; i < points.length; i++)
  48. 		{
  49. 			Point a = points[i];
  50. 			Point b = points[(i+1)%points.length];
  51. 			Point c = points[(i+2)%points.length];
  52. 			if(a.to(b).crossProduct(b.to(p)) > 0 && b.to(p).crossProduct(b.to(c)) > 0)
  53. 			{
  54. 				ret.from = fix(b.to(p).direction() - Math.PI / 2);
  55. 			}
  56.  
  57. 			if(a.to(b).crossProduct(b.to(p)) < 0 && b.to(p).crossProduct(b.to(c)) < 0)
  58. 			{
  59. 				ret.to = fix(b.to(p).direction() + Math.PI / 2);
  60. 			}
  61. 		}
  62. 		return ret;
  63. 	}
  64.  
  65. 	Point[] ConvexHull(Point[] points)
  66. 	{
  67. 		for(int i = 1; i < points.length; i++)
  68. 			if(points[i].y < points[0].y || (points[i].y == points[0].y && points[i].x < points[0].x))
  69. 			{
  70. 				Point t = points[0];
  71. 				points[0] = points[i];
  72. 				points[i] = t;
  73. 			}
  74. 		for(int iteration = 1; iteration <= points.length; iteration ++)
  75. 			for(int i = 1; i < points.length-1; i++)
  76. 				if(points[0].to(points[i]).crossProduct(points[0].to(points[i+1])) < 0)
  77. 				{
  78. 					Point t = points[i];
  79. 					points[i] = points[i+1];
  80. 					points[i+1] = t;
  81. 				}
  82. 		int z = 2;
  83. 		for(int i = 2; i < points.length; i++)
  84. 		{
  85. 			while(points[z-2].to(points[z-1]).crossProduct(points[z-1].to(points[i])) < 0)
  86. 				z --;
  87. 			points[z] = points[i];
  88. 			z ++;
  89. 		}
  90. 		Point[] ret = new Point[z];
  91. 		for(int i = 0; i < z; i++)
  92. 			ret[i] = points[i];
  93. 		return ret;
  94. 	}
  95.  
  96. 	int n;
  97. 	Range[] r;
  98. 	double[][][][] dp_mem;
  99. 	boolean[][][][] done;
  100.  
  101. 	double dp(int haveAtLeastOne, int current, int leftIndex, int rightIndex)
  102. 	{
  103. 		if(current == n)
  104. 			return 0.0;
  105. 		if(done[haveAtLeastOne][current][leftIndex][rightIndex])
  106. 			return dp_mem[haveAtLeastOne][current][leftIndex][rightIndex];
  107. 		double ret = 0.0;
  108. 		// choose this
  109. 		{
  110. 			if(haveAtLeastOne == 0)
  111. 			{
  112. 				if(r[current].from < 180.0)
  113. 				{
  114. 					ret += r[current].prob * dp(1, current + 1, current, current);
  115. 				}
  116. 			}
  117. 			else
  118. 			{
  119. 				if(r[leftIndex].from > r[rightIndex].to)
  120. 				{
  121. 					if(r[current].to < r[current].from && r[current].to > r[leftIndex].from)
  122. 						ret += r[current].prob * 1.0;
  123. 					else
  124. 						ret += r[current].prob * dp(1, current + 1, leftIndex, rightIndex);
  125. 				}
  126. 				else
  127. 				{
  128. 					if(r[current].from < r[rightIndex].to)
  129. 					{
  130. 						if(r[current].to < r[current].from)
  131. 						{
  132. 							if(r[current].to > r[leftIndex].from)
  133. 								ret += r[current].prob * 1.0;
  134. 							else
  135. 								ret += r[current].prob * dp(1, current + 1, leftIndex, current);
  136. 						}
  137. 						else
  138. 						{
  139. 							if(r[current].to > r[rightIndex].to)
  140. 								ret += r[current].prob * dp(1, current + 1, leftIndex, current);
  141. 							else
  142. 								ret += r[current].prob * dp(1, current + 1, leftIndex, rightIndex);
  143. 						}
  144. 					}
  145. 					else
  146. 					{
  147. 						if(r[current].from < 180.0)
  148. 						{
  149. 							ret += r[current].prob * dp(1, current + 1, current, current);
  150. 						}
  151. 					}
  152. 				}
  153. 			}
  154.  
  155. 		}
  156. 		// not choose this
  157. 		{
  158. 			ret += (1 - r[current].prob) * dp(haveAtLeastOne, current + 1, leftIndex, rightIndex);
  159. 		}
  160.  
  161. 		dp_mem[haveAtLeastOne][current][leftIndex][rightIndex] = ret;
  162. 		done[haveAtLeastOne][current][leftIndex][rightIndex] = true;
  163. 		return ret;
  164. 	}
  165.  
  166. 	public double totallyCovered(int[] redX, int[] redY, int[] prob, int[] blueX, int[] blueY)
  167. 	{
  168. 		int nRed = redX.length;
  169. 		int nBlue = blueX.length;
  170.  
  171. 		Point[] points = new Point[nBlue];
  172. 		for(int i = 0; i < nBlue; i++)
  173. 			points[i] = new Point(blueX[i], blueY[i]);
  174. 		points = ConvexHull(points);
  175.  
  176. 		r = new Range[nRed];
  177. 		n = 0;
  178. 		for(int i = 0; i < redX.length; i++)
  179. 		{
  180. 			Point p = new Point(redX[i], redY[i]);
  181. 			Range t = coverRange(points, p);
  182. 			if(t.from != t.to)
  183. 			{
  184. 				t.prob = prob[i] / 1000.0;
  185. 				r[n] = t;
  186. 				n ++;
  187. 			}
  188. 		}
  189.  
  190. 		for(int iteration = 1; iteration <= n; iteration ++)
  191. 			for(int i = 0; i < n-1; i++)
  192. 				if(r[i].from > r[i+1].from)
  193. 				{
  194. 					Range t = r[i];
  195. 					r[i] = r[i+1];
  196. 					r[i+1] = t;
  197. 				}
  198.  
  199. 		dp_mem = new double[2][n][n][n];
  200. 		done = new boolean[2][n][n][n];
  201. 		for(int i = 0; i < 2; i++)
  202. 			for(int j = 0; j < n; j++)
  203. 				for(int k = 0; k < n; k++)
  204. 					for(int l = 0; l < n; l++)
  205. 						done[i][j][k][l] = false;
  206.  
  207. 		return dp(0, 0, 0, 0);
  208. 	}
  209. }
  210.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class BichromeSky is public, should be declared in a file named BichromeSky.java
public class BichromeSky
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/Yq4ReK
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!