Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigDecimal;
- import java.math.MathContext;
- import java.util.*;
- public class C {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n, m;
- n = in.nextInt();
- m = in.nextInt();
- int[] lDots = new int[n + 1];
- for (int i = 0; i <= n; ++i) {
- lDots[i] = in.nextInt();
- }
- Tuple[] lLines = new Tuple[n];
- for (int i = 0; i < n; i++) {
- lLines[i] = new Tuple(in.nextBigDecimal(), in.nextBigDecimal(), in.nextBigDecimal());
- }
- int[] rDots = new int[m + 1];
- for (int i = 0; i <= m; ++i) {
- rDots[i] = in.nextInt();
- }
- Tuple[] rLines = new Tuple[m];
- for (int i = 0; i < m; i++) {
- rLines[i] = new Tuple(in.nextBigDecimal(), in.nextBigDecimal(), in.nextBigDecimal());
- }
- Set<Integer> allDots = new TreeSet<>();
- for (int i = 0; i <= n; i++) {
- allDots.add(lDots[i]);
- }
- for (int i = 0; i <= m; i++) {
- allDots.add(rDots[i]);
- }
- int[] merged = new int[allDots.size()];
- int j = 0;
- for (Integer a : allDots) {
- merged[j] = a;
- j++;
- }
- BigDecimal res = new BigDecimal(0);
- for (int i = 1; i < merged.length; i++) {
- int curIdLeft = Arrays.binarySearch(lDots, merged[i - 1]);
- if(curIdLeft < 0) {
- curIdLeft = -(curIdLeft + 1);
- }
- // BigDecimal I1 = calculate(curIdLeft, lDots, lLines);
- int curIdRight = Arrays.binarySearch(rDots, merged[i - 1]);
- if(curIdRight < 0) {
- curIdRight = -(curIdRight + 1);
- }
- Tuple newCof = lLines[curIdLeft].subtract(rLines[curIdRight]);
- res = res.add(calculate(newCof, merged[i - 1], merged[i]));
- // BigDecimal I2 = calculate(curIdRight, rDots, rLines);
- // res = res.add(I1.subtract(I2).abs());
- }
- System.out.println(res);
- }
- public static BigDecimal calculate(Tuple cur, int left, int right) {
- Pair solution = solveEquation(cur);
- if (notInside(solution.x1, left, right)) {
- solution.x1 = null;
- }
- if (notInside(solution.x2, left, right)) {
- solution.x2 = null;
- }
- if (solution.x2 != null && solution.x1 == null) {
- solution.x1 = solution.x2;
- solution.x2 = null;
- }
- if (solution.x1 == null) {
- if (cur.a.compareTo(BigDecimal.valueOf(0)) == 0) {
- cur.c = cur.c.abs();
- return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
- }
- if (func(cur, (double) (left + right) / 2.0).compareTo(BigDecimal.valueOf(0)) < 0) {
- return calculateIntegral(cur.negate(), BigDecimal.valueOf(left), BigDecimal.valueOf(right));
- } else {
- return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
- }
- }
- if (solution.x2 == null) {
- if (notInside(solution.x1, left, right)) {
- if (func(cur, (double) (left + right) / 2.0).compareTo(BigDecimal.valueOf(0)) < 0) {
- cur = cur.negate();
- return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
- }
- return calculateIntegral(cur, BigDecimal.valueOf(left), BigDecimal.valueOf(right));
- }
- if (func(cur, (double) left).compareTo(BigDecimal.valueOf(0)) < 0) {
- return calculateIntegral(cur.negate(),
- BigDecimal.valueOf(left), solution.x1).add(calculateIntegral(cur, solution.x1, BigDecimal.valueOf(right)));
- }
- return calculateIntegral(cur,
- BigDecimal.valueOf(left), solution.x1).add(calculateIntegral(cur.negate(), solution.x1, BigDecimal.valueOf(right)));
- }
- if (cur.a.compareTo(BigDecimal.valueOf(0)) < 0) {
- return calculateIntegral(cur.negate(), BigDecimal.valueOf(left), solution.x1).add(
- calculateIntegral(cur, solution.x1, solution.x2).add(calculateIntegral(cur.negate(), solution.x2, BigDecimal.valueOf(right)))
- );
- }
- return calculateIntegral(cur, BigDecimal.valueOf(left), solution.x1).add(
- calculateIntegral(cur.negate(), solution.x1, solution.x2).add(calculateIntegral(cur, solution.x2, BigDecimal.valueOf(right)))
- );
- }
- public static boolean notInside(BigDecimal x1, int left, int right) {
- if (x1 == null) return false;
- return x1.compareTo(BigDecimal.valueOf(left)) <= 0 || x1.compareTo(BigDecimal.valueOf(right)) >= 0;
- }
- public static BigDecimal func(Tuple a, double x) {
- return a.a.multiply(BigDecimal.valueOf(x).pow(2)).add(a.b.multiply(BigDecimal.valueOf(x))).add(a.c);
- }
- public static BigDecimal calculateIntegral(Tuple a, BigDecimal left, BigDecimal right) {
- return right.pow(3).multiply(a.a).divide(BigDecimal.valueOf(3), 20, BigDecimal.ROUND_CEILING)
- .add(right.pow(2).multiply(a.b).divide(BigDecimal.valueOf(2), 20, BigDecimal.ROUND_CEILING))
- .add(right.multiply(a.c)).subtract(left.pow(3).multiply(a.a).divide(BigDecimal.valueOf(3), 20, BigDecimal.ROUND_CEILING)
- .add(left.pow(2).multiply(a.b).divide(BigDecimal.valueOf(2), 20, BigDecimal.ROUND_CEILING))
- .add(left.multiply(a.c)));
- }
- public static Pair solveEquation(Tuple cur) {
- BigDecimal a = cur.a;
- BigDecimal b = cur.b;
- BigDecimal c = cur.c;
- if (a.intValue() == 0) {
- if (b.intValue() == 0) {
- return new Pair(null, null);
- }
- return new Pair(c.negate().divide(b, 20, BigDecimal.ROUND_HALF_UP), null);
- }
- BigDecimal D = b.multiply(b).subtract(a.multiply(c).multiply(BigDecimal.valueOf(4)));
- if (D.compareTo(BigDecimal.valueOf(0)) == 0) {
- return new Pair(b.negate().add(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)),
- 20, BigDecimal.ROUND_CEILING), null);
- }
- if (D.compareTo(BigDecimal.valueOf(0)) < 0) {
- return new Pair(null, null);
- }
- BigDecimal x1 = b.negate().add(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)), 20, BigDecimal.ROUND_CEILING);
- BigDecimal x2 = b.negate().subtract(BigDecimal.valueOf(Math.sqrt(D.doubleValue()))).divide(a.multiply(BigDecimal.valueOf(2)),
- BigDecimal.ROUND_CEILING);
- return new Pair(x1.min(x2), x1.max(x2));
- }
- }
- class Pair {
- BigDecimal x1;
- BigDecimal x2;
- public Pair(BigDecimal x1, BigDecimal x2) {
- this.x1 = x1;
- this.x2 = x2;
- }
- }
- class Tuple {
- BigDecimal a;
- BigDecimal b;
- BigDecimal c;
- public Tuple negate() {
- return new Tuple(a.negate(), b.negate(), c.negate());
- }
- public Tuple subtract(Tuple t) {
- return new Tuple(a.subtract(t.a), b.subtract(t.b), c.subtract(t.c));
- }
- public Tuple(BigDecimal a, BigDecimal b, BigDecimal c) {
- this.a = a;
- this.b = b;
- this.c = c;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement