Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.41 KB | None | 0 0
  1. import java.math.BigDecimal;
  2. import java.math.MathContext;
  3. import java.util.*;
  4.  
  5. public class C {
  6. public static void main(String[] args) {
  7. Scanner in = new Scanner(System.in);
  8. int n, m;
  9. n = in.nextInt();
  10. m = in.nextInt();
  11. int[] lDots = new int[n + 1];
  12. for (int i = 0; i <= n; ++i) {
  13. lDots[i] = in.nextInt();
  14. }
  15. Tuple[] lLines = new Tuple[n];
  16. for (int i = 0; i < n; i++) {
  17. lLines[i] = new Tuple(in.nextBigDecimal(), in.nextBigDecimal(), in.nextBigDecimal());
  18. }
  19. int[] rDots = new int[m + 1];
  20. for (int i = 0; i <= m; ++i) {
  21. rDots[i] = in.nextInt();
  22. }
  23. Tuple[] rLines = new Tuple[m];
  24. for (int i = 0; i < m; i++) {
  25. rLines[i] = new Tuple(in.nextBigDecimal(), in.nextBigDecimal(), in.nextBigDecimal());
  26. }
  27.  
  28. Set<Integer> allDots = new TreeSet<>();
  29. for (int i = 0; i <= n; i++) {
  30. allDots.add(lDots[i]);
  31. }
  32. for (int i = 0; i <= m; i++) {
  33. allDots.add(rDots[i]);
  34. }
  35. int[] merged = new int[allDots.size()];
  36. int j = 0;
  37. for (Integer a : allDots) {
  38. merged[j] = a;
  39. j++;
  40. }
  41. BigDecimal res = new BigDecimal(0);
  42. for (int i = 1; i < merged.length; i++) {
  43. int curIdLeft = Arrays.binarySearch(lDots, merged[i - 1]);
  44. if(curIdLeft < 0) {
  45. curIdLeft = -(curIdLeft + 1);
  46. }
  47. // BigDecimal I1 = calculate(curIdLeft, lDots, lLines);
  48. int curIdRight = Arrays.binarySearch(rDots, merged[i - 1]);
  49. if(curIdRight < 0) {
  50. curIdRight = -(curIdRight + 1);
  51. }
  52. Tuple newCof = lLines[curIdLeft].subtract(rLines[curIdRight]);
  53. res = res.add(calculate(newCof, merged[i - 1], merged[i]));
  54. // BigDecimal I2 = calculate(curIdRight, rDots, rLines);
  55. // res = res.add(I1.subtract(I2).abs());
  56. }
  57. System.out.println(res);
  58. }
  59.  
  60. public static BigDecimal calculate(Tuple cur, int left, int right) {
  61. Pair solution = solveEquation(cur);
  62.  
  63. if (notInside(solution.x1, left, right)) {
  64. solution.x1 = null;
  65. }
  66. if (notInside(solution.x2, left, right)) {
  67. solution.x2 = null;
  68. }
  69.  
  70. if (solution.x2 != null && solution.x1 == null) {
  71. solution.x1 = solution.x2;
  72. solution.x2 = null;
  73. }
  74. if (solution.x1 == null) {
  75. if (cur.a.compareTo(BigDecimal.valueOf(0)) == 0) {
  76. cur.c = cur.c.abs();
  77. return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
  78. }
  79. if (func(cur, (double) (left + right) / 2.0).compareTo(BigDecimal.valueOf(0)) < 0) {
  80. return calculateIntegral(cur.negate(), BigDecimal.valueOf(left), BigDecimal.valueOf(right));
  81. } else {
  82. return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
  83.  
  84. }
  85. }
  86. if (solution.x2 == null) {
  87. if (notInside(solution.x1, left, right)) {
  88. if (func(cur, (double) (left + right) / 2.0).compareTo(BigDecimal.valueOf(0)) < 0) {
  89. cur = cur.negate();
  90. return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
  91. }
  92. return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
  93. }
  94. if (func(cur, (double) left).compareTo(BigDecimal.valueOf(0)) < 0) {
  95. return calculateIntegral(cur.negate(),
  96. BigDecimal.valueOf(left), solution.x1).add(calculateIntegral(cur, solution.x1, BigDecimal.valueOf(right)));
  97. }
  98. return calculateIntegral(cur,
  99. BigDecimal.valueOf(left), solution.x1).add(calculateIntegral(cur.negate(), solution.x1, BigDecimal.valueOf(right)));
  100. }
  101. if (cur.a.compareTo(BigDecimal.valueOf(0)) < 0) {
  102. return calculateIntegral(cur.negate(), BigDecimal.valueOf(left), solution.x1).add(
  103. calculateIntegral(cur, solution.x1, solution.x2).add(calculateIntegral(cur.negate(), solution.x2, BigDecimal.valueOf(right)))
  104. );
  105. }
  106. return calculateIntegral(cur, BigDecimal.valueOf(left), solution.x1).add(
  107. calculateIntegral(cur.negate(), solution.x1, solution.x2).add(calculateIntegral(cur, solution.x2, BigDecimal.valueOf(right)))
  108. );
  109. }
  110.  
  111. public static boolean notInside(BigDecimal x1, int left, int right) {
  112. if (x1 == null) return false;
  113. return x1.compareTo(BigDecimal.valueOf(left)) <= 0 || x1.compareTo(BigDecimal.valueOf(right)) >= 0;
  114. }
  115.  
  116. public static BigDecimal func(Tuple a, double x) {
  117. return a.a.multiply(BigDecimal.valueOf(x).pow(2)).add(a.b.multiply(BigDecimal.valueOf(x))).add(a.c);
  118. }
  119.  
  120. public static BigDecimal calculateIntegral(Tuple a, BigDecimal left, BigDecimal right) {
  121. return right.pow(3).multiply(a.a).divide(BigDecimal.valueOf(3), 20, BigDecimal.ROUND_CEILING)
  122. .add(right.pow(2).multiply(a.b).divide(BigDecimal.valueOf(2), 20, BigDecimal.ROUND_CEILING))
  123. .add(right.multiply(a.c)).subtract(left.pow(3).multiply(a.a).divide(BigDecimal.valueOf(3), 20, BigDecimal.ROUND_CEILING)
  124. .add(left.pow(2).multiply(a.b).divide(BigDecimal.valueOf(2), 20, BigDecimal.ROUND_CEILING))
  125. .add(left.multiply(a.c)));
  126. }
  127.  
  128. public static Pair solveEquation(Tuple cur) {
  129. BigDecimal a = cur.a;
  130. BigDecimal b = cur.b;
  131. BigDecimal c = cur.c;
  132. if (a.intValue() == 0) {
  133. if (b.intValue() == 0) {
  134. return new Pair(null, null);
  135. }
  136. return new Pair(c.negate().divide(b, 20, BigDecimal.ROUND_HALF_UP), null);
  137. }
  138. BigDecimal D = b.multiply(b).subtract(a.multiply(c).multiply(BigDecimal.valueOf(4)));
  139. if (D.compareTo(BigDecimal.valueOf(0)) == 0) {
  140. return new Pair(b.negate().add(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)),
  141. 20, BigDecimal.ROUND_CEILING), null);
  142. }
  143. if (D.compareTo(BigDecimal.valueOf(0)) < 0) {
  144. return new Pair(null, null);
  145.  
  146. }
  147. BigDecimal x1 = b.negate().add(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)), 20, BigDecimal.ROUND_CEILING);
  148. BigDecimal x2 = b.negate().subtract(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)),
  149. BigDecimal.ROUND_CEILING);
  150. return new Pair(x1.min(x2), x1.max(x2));
  151. }
  152. }
  153.  
  154. class Pair {
  155. BigDecimal x1;
  156. BigDecimal x2;
  157.  
  158. public Pair(BigDecimal x1, BigDecimal x2) {
  159. this.x1 = x1;
  160. this.x2 = x2;
  161. }
  162. }
  163.  
  164. class Tuple {
  165. BigDecimal a;
  166. BigDecimal b;
  167. BigDecimal c;
  168.  
  169. public Tuple negate() {
  170. return new Tuple(a.negate(), b.negate(), c.negate());
  171. }
  172.  
  173. public Tuple subtract(Tuple t) {
  174. return new Tuple(a.subtract(t.a), b.subtract(t.b), c.subtract(t.c));
  175. }
  176.  
  177. public Tuple(BigDecimal a, BigDecimal b, BigDecimal c) {
  178. this.a = a;
  179. this.b = b;
  180. this.c = c;
  181. }
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement