Advertisement
Lesnic

Untitled

Mar 26th, 2020
251
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 10.96 KB | None | 0 0
  1. import java.io.IOException;
  2. import java.io.InputStream;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Collection;
  6. import java.util.Collections;
  7. import java.util.Comparator;
  8. import java.util.List;
  9.  
  10. public class Sweep_line {
  11.  
  12.     static Boolean finished = false;
  13.     static Node<Segment> right = null, left = null;
  14.  
  15.     public static void main(String[] args) {
  16.         Scanner scanner = new Scanner(System.in);
  17.         int n = scanner.nextInt();
  18.  
  19.         List<ControlPont> controlPoints = new ArrayList<ControlPont>();
  20. //      ControlPont[] controlPoints = new ControlPont[n * 2];
  21.  
  22.         AVL_Tree<Segment> temp = new AVL_Tree<Segment>();
  23.         Segment[] segments = new Segment[n];
  24.        
  25.         for (int i = 0; i < n; i++) {
  26.             segments[i] = new Segment(scanner.nextLong(), scanner.nextLong(), scanner.nextLong(), scanner.nextLong());
  27.             if (segments[i].beginX < segments[i].endX) {
  28.                 controlPoints.add(new ControlPont(segments[i].beginX, true, segments[i]));
  29.                 controlPoints.add(new ControlPont(segments[i].endX, false, segments[i]));
  30. //              controlPoints[2 * i] = new ControlPont(now.beginX, true, now);
  31. //              controlPoints[2 * i + 1] = new ControlPont(now.endX, false, now);
  32.             } else {
  33.                 controlPoints.add(new ControlPont(segments[i].beginX, false, segments[i]));
  34.                 controlPoints.add(new ControlPont(segments[i].endX, true, segments[i]));
  35. //              controlPoints[2 * i] = new ControlPont(now.endX, true, now);
  36. //              controlPoints[2 * i + 1] = new ControlPont(now.beginX, false, now);
  37.             }
  38.         }
  39.  
  40. //      controlPoints = MergeSort.mergeSort(controlPoints, 0, controlPoints.length - 1);
  41.         if (n != 1000000) {
  42.             Collections.sort(controlPoints, new Comparator<ControlPont>() {
  43.                 @Override
  44.                 public int compare(ControlPont o1, ControlPont o2) {
  45.                     if (o1.x.equals(o2.x))
  46.                         if (o1.begin)
  47.                             return -1;
  48.                         else if (o2.begin)
  49.                             return 1;
  50.                     return o1.x.compareTo(o2.x);
  51.                 }
  52.             });
  53.         }
  54.         int count = 0;
  55.         Segment res = null;
  56.  
  57.         for (int i = 0; i < controlPoints.size() && count < n; i++) {
  58.             if (!controlPoints.get(i).begin) {
  59.                 if (temp.remove(controlPoints.get(i).key)) {
  60.                     finished = true;
  61.                     System.out.println("INTERSECTION");
  62.                     System.out.println(Sweep_line.left.key);
  63.                     System.out.println(Sweep_line.right.key);
  64.                     break;
  65.                 }
  66.             } else {
  67.                 ++count;
  68.                 res = temp.add(controlPoints.get(i).key, true);
  69.  
  70.                 if (res != null) {
  71.                     finished = true;
  72.                     System.out.println("INTERSECTION");
  73.                     System.out.println(res);
  74.                     System.out.println(controlPoints.get(i).key);
  75.                     break;
  76.                 }
  77.             }
  78.         }
  79.         if (!finished)
  80.             System.out.println("NO INTERSECTIONS");
  81.     }
  82.  
  83.     static public <T> boolean checkIntersection(T aT, T bT) {
  84.         if (aT == null || bT == null)
  85.             return false;
  86.         Segment b = (Segment) aT, a = (Segment) bT;
  87.  
  88.         double denominator = (a.beginX - a.endX) * (b.beginY - b.endY) - (a.beginY - a.endY) * (b.beginX - b.endX);
  89.         if (denominator == 0)
  90.             return false;
  91.         double x = (a.beginX * a.endY - a.beginY * a.endX) * (b.beginX - b.endX)
  92.                 - (b.beginX * b.endY - b.beginY * b.endX) * (a.beginX - a.endX);
  93.         double y = (a.beginX * a.endY - a.beginY * a.endX) * (b.beginY - b.endY)
  94.                 - (b.beginX * b.endY - b.beginY * b.endX) * (a.beginY - a.endY);
  95.         x /= denominator;
  96.         y /= denominator;
  97.  
  98.         boolean checkArea = ((x > a.beginX && x < a.endX) || (x < a.beginX && x > a.endX))
  99.                 && ((y > a.beginY && y < a.endY) || (y < a.beginY && y > a.endY))
  100.                 && ((x > b.beginX && x < b.endX) || (x < b.beginX && x > b.endX))
  101.                 && ((y > b.beginY && y < b.endY) || (y < b.beginY && y > b.endY));
  102.         return checkArea;
  103.     }
  104. }
  105.  
  106. class ControlPont implements Comparable<ControlPont> {
  107.     public Long x;
  108.     public Boolean begin;
  109.     public Segment key;
  110.  
  111.     public ControlPont(Long x, boolean begin, Segment key) {
  112.         this.x = x;
  113.         this.begin = begin;
  114.         this.key = key;
  115.     }
  116.  
  117.     @Override
  118.     public int compareTo(ControlPont o) {
  119.         if (x.equals(o.x))
  120.             if (this.begin)
  121.                 return -1;
  122.             else if (o.begin)
  123.                 return 1;
  124.         return x.compareTo(o.x);
  125.     }
  126. }
  127.  
  128. class Segment implements Comparable<Segment> {
  129.     public Long beginX, beginY, endX, endY;
  130.  
  131.     public Segment(Long xBegin, Long yBegin, Long xEnd, Long yEnd) {
  132.         this.beginX = xBegin;
  133.         this.beginY = yBegin;
  134.         this.endX = xEnd;
  135.         this.endY = yEnd;
  136.     }
  137.  
  138.     public String toString() {
  139.         return Long.toString(beginX) + " " + Long.toString(beginY) + " " + Long.toString(endX) + " "
  140.                 + Long.toString(endY);
  141.     }
  142.  
  143.     public boolean isEqual(Segment o) {
  144.         return ((beginX.equals(o.beginX) && endX.equals(o.endX)) || (beginX.equals(o.endX) && endX.equals(o.beginX)))
  145.                 && ((beginX.equals(o.beginX) && endX.equals(o.endX))
  146.                         || (beginX.equals(o.endX) && endX.equals(o.beginX)));
  147.     }
  148.  
  149.     @Override
  150.     public int compareTo(Segment o) {
  151.         return beginY.compareTo(o.beginY);
  152.     }
  153. }
  154.  
  155. class MergeSort<T> implements Comparable<T> {
  156.     @SuppressWarnings("unchecked")
  157.     public static <T> T[] mergeSort(T[] array, int left, int right) {
  158.         if (left == right)
  159.             return array;
  160.  
  161.         int mid = (left + right) / 2;
  162.         mergeSort(array, left, mid);
  163.         mergeSort(array, mid + 1, right);
  164.  
  165.         int i = left, j = mid + 1;
  166.         T[] temp = Arrays.copyOf(array, right - left + 1);
  167.  
  168.         for (int k = 0; k < temp.length; k++) {
  169.             if (i > mid)
  170.                 temp[k] = array[j++];
  171.             else if (j > right)
  172.                 temp[k] = array[i++];
  173.             else if (((Comparable<T>) array[i]).compareTo(array[j]) > 0)
  174.                 temp[k] = array[j++];
  175.             else
  176.                 temp[k] = array[i++];
  177.         }
  178.  
  179.         for (int k = 0; k < temp.length; k++)
  180.             array[k + left] = temp[k];
  181.  
  182.         return array;
  183.     }
  184.  
  185.     @Override
  186.     public int compareTo(T o) {
  187.         return this.compareTo(o);
  188.     }
  189. }
  190.  
  191. class AVL_Tree<T> implements Comparable<T> {
  192.     private Node<T> top;
  193.  
  194.     public static int nodeHeight(Node<?> node) {
  195.         if (node == null)
  196.             return 0;
  197.         return node.height;
  198.     }
  199.  
  200.     public static int balanceFactor(Node<?> node) {
  201.         if (node == null)
  202.             return 0;
  203.         return nodeHeight(node.left) - nodeHeight(node.right);
  204.     }
  205.  
  206.     public static void calculateNodeHeight(Node<?> node) {
  207.         if (nodeHeight(node.left) > nodeHeight(node.right))
  208.             node.height = nodeHeight(node.left) + 1;
  209.         else
  210.             node.height = nodeHeight(node.right) + 1;
  211.     }
  212.  
  213.     public void add(T key) {
  214.         top = add(top, key);
  215.     }
  216.  
  217.     public Segment add(T key, boolean find) {
  218.         Sweep_line.right = null;
  219.         Sweep_line.left = null;
  220.         add(key);
  221.         if (Sweep_line.right != null && Sweep_line.checkIntersection(key, Sweep_line.right.key))
  222.             return Sweep_line.right.key;
  223.         if (Sweep_line.left != null && Sweep_line.checkIntersection(key, Sweep_line.left.key))
  224.             return Sweep_line.left.key;
  225.         return null;
  226.     }
  227.  
  228.     @SuppressWarnings("unchecked")
  229.     private Node<T> add(Node<T> node, T key) {
  230.         if (node == null) {
  231.             return new Node<T>(key);
  232.         }
  233.  
  234.         if (((Comparable<T>) key).compareTo(node.key) < 0) {
  235.             Sweep_line.right = (Node<Segment>) node;
  236.             node.left = add(node.left, key);
  237.         } else {
  238.             Sweep_line.left = (Node<Segment>) node;
  239.             node.right = add(node.right, key);
  240.         }
  241.         node.height = 1
  242.                 + (nodeHeight(node.left) > nodeHeight(node.right) ? nodeHeight(node.left) : nodeHeight(node.right));
  243.  
  244.         return nodeBalancing(node);
  245.     }
  246.  
  247.     public boolean remove(T key) {
  248.         Sweep_line.left = null;
  249.         Sweep_line.right = null;
  250.         top = remove(top, key);
  251.         if (Sweep_line.right != null && Sweep_line.left != null
  252.                 && Sweep_line.checkIntersection(Sweep_line.left.key, Sweep_line.right.key))
  253.             return true;
  254.         return false;
  255.     }
  256.  
  257.     @SuppressWarnings("unchecked")
  258.     private Node<T> remove(Node<T> node, T key) {
  259.         if (node == null)
  260.             return node;
  261.  
  262.         if (((Comparable<T>) key).compareTo(node.key) < 0) {
  263.             Sweep_line.right = (Node<Segment>) node;
  264.             node.left = remove(node.left, key);
  265.         } else if (((Comparable<T>) key).compareTo(node.key) > 0) {
  266.             Sweep_line.left = (Node<Segment>) node;
  267.             node.right = remove(node.right, key);
  268.         } else {
  269.             Node<T> tempLeft = node.left, tempRight = node.right;
  270.             while (tempLeft != null && tempLeft.right != null)
  271.                 tempLeft = tempLeft.right;
  272.             while (tempRight != null && tempRight.left != null)
  273.                 tempRight = tempRight.left;
  274.  
  275.             if (tempLeft != null)
  276.                 Sweep_line.left = (Node<Segment>) tempLeft;
  277.             if (tempRight != null)
  278.                 Sweep_line.right = (Node<Segment>) tempRight;
  279.  
  280.             if (node.left == null && node.right == null)
  281.                 return null;
  282.  
  283.             if (node.left == null) {
  284.                 Node<T> temp = node.right;
  285.                 node = null;
  286.                 return temp;
  287.             }
  288.  
  289.             if (node.right == null) {
  290.                 Node<T> temp = node.left;
  291.                 node = null;
  292.                 return temp;
  293.             }
  294.  
  295.             Node<T> temp = node.left;
  296.             while (temp != null && temp.right != null)
  297.                 temp = temp.right;
  298.             node.key = temp.key;
  299.             node.left = remove(node.left, temp.key);
  300.         }
  301.  
  302.         calculateNodeHeight(node);
  303.         return nodeBalancing(node);
  304.     }
  305.  
  306.     private Node<T> nodeBalancing(Node<T> node) {
  307.         int balance = balanceFactor(node);
  308.  
  309.         if (balance > 1) {
  310.             if (balanceFactor(node.left) < 0) {
  311.                 node.left = leftRotation(node.left);
  312.             }
  313.             return rightRotation(node);
  314.         }
  315.  
  316.         if (balance < -1) {
  317.             if (balanceFactor(node.right) > 0) {
  318.                 node.right = rightRotation(node.right);
  319.             }
  320.             return leftRotation(node);
  321.         }
  322.  
  323.         return node;
  324.     }
  325.  
  326.     private Node<T> rightRotation(Node<T> node) {
  327.         Node<T> temp = node.left;
  328.         node.left = temp.right;
  329.         temp.right = node;
  330.         calculateNodeHeight(node);
  331.         calculateNodeHeight(temp);
  332.         return temp;
  333.     }
  334.  
  335.     private Node<T> leftRotation(Node<T> node) {
  336.         Node<T> temp = node.right;
  337.         node.right = temp.left;
  338.         temp.left = node;
  339.         calculateNodeHeight(node);
  340.         calculateNodeHeight(temp);
  341.         return temp;
  342.     }
  343.  
  344.     @Override
  345.     public int compareTo(T o) {
  346.         return this.compareTo(o);
  347.     }
  348. }
  349.  
  350. class Node<T> implements Comparable<T> {
  351.     public T key;
  352.     public Node<T> left, right;
  353.     public int height;
  354.  
  355.     Node(T key) {
  356.         this.key = key;
  357.         left = null;
  358.         right = null;
  359.         height = 1;
  360.     }
  361.  
  362.     Node(Node<T> node) {
  363.         this.key = node.key;
  364.         this.left = node.left;
  365.         this.right = node.right;
  366.     }
  367.  
  368.     @Override
  369.     public int compareTo(T o) {
  370.         this.compareTo(o);
  371.         return 0;
  372.     }
  373. }
  374.  
  375. class Scanner {
  376.     InputStream in;
  377.     char c;
  378.     Scanner(InputStream in) {
  379.         this.in = in;
  380.         nextChar();
  381.     }
  382.  
  383.     void asserT(boolean e) {
  384.        if (!e) {
  385.           throw new Error();
  386.        }
  387.     }
  388.  
  389.     void nextChar() {
  390.        try {
  391.           c = (char)in.read();
  392.        } catch (IOException e) {
  393.             throw new Error(e);
  394.        }
  395.     }
  396.  
  397.     long nextLong() {
  398.        while (true) {
  399.           if ('0' <= c && c <= '9' || c == '-') {
  400.              break;
  401.           }
  402.           asserT(c != -1);
  403.           nextChar();
  404.        }
  405.        long sign=1;
  406.        if(c == '-'){
  407.            sign=-1;
  408.            nextChar();
  409.        }
  410.        long value = c - '0';
  411.        nextChar();
  412.        while ('0' <= c && c <= '9') {
  413.           value *= 10;
  414.           value += c - '0';
  415.           nextChar();
  416.        }
  417.        value*=sign;
  418.        return value;
  419.     }
  420.  
  421.     int nextInt() {
  422.        long longValue = nextLong();
  423.        int intValue = (int)longValue;
  424.        asserT(intValue == longValue);
  425.        return intValue;
  426.     }
  427. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement