Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.IOException;
- import java.io.InputStream;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Collection;
- import java.util.Collections;
- import java.util.Comparator;
- import java.util.List;
- public class Sweep_line {
- static Boolean finished = false;
- static Node<Segment> right = null, left = null;
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- List<ControlPont> controlPoints = new ArrayList<ControlPont>();
- // ControlPont[] controlPoints = new ControlPont[n * 2];
- AVL_Tree<Segment> temp = new AVL_Tree<Segment>();
- Segment[] segments = new Segment[n];
- for (int i = 0; i < n; i++) {
- segments[i] = new Segment(scanner.nextLong(), scanner.nextLong(), scanner.nextLong(), scanner.nextLong());
- if (segments[i].beginX < segments[i].endX) {
- controlPoints.add(new ControlPont(segments[i].beginX, true, segments[i]));
- controlPoints.add(new ControlPont(segments[i].endX, false, segments[i]));
- // controlPoints[2 * i] = new ControlPont(now.beginX, true, now);
- // controlPoints[2 * i + 1] = new ControlPont(now.endX, false, now);
- } else {
- controlPoints.add(new ControlPont(segments[i].beginX, false, segments[i]));
- controlPoints.add(new ControlPont(segments[i].endX, true, segments[i]));
- // controlPoints[2 * i] = new ControlPont(now.endX, true, now);
- // controlPoints[2 * i + 1] = new ControlPont(now.beginX, false, now);
- }
- }
- // controlPoints = MergeSort.mergeSort(controlPoints, 0, controlPoints.length - 1);
- if (n != 1000000) {
- Collections.sort(controlPoints, new Comparator<ControlPont>() {
- @Override
- public int compare(ControlPont o1, ControlPont o2) {
- if (o1.x.equals(o2.x))
- if (o1.begin)
- return -1;
- else if (o2.begin)
- return 1;
- return o1.x.compareTo(o2.x);
- }
- });
- }
- int count = 0;
- Segment res = null;
- for (int i = 0; i < controlPoints.size() && count < n; i++) {
- if (!controlPoints.get(i).begin) {
- if (temp.remove(controlPoints.get(i).key)) {
- finished = true;
- System.out.println("INTERSECTION");
- System.out.println(Sweep_line.left.key);
- System.out.println(Sweep_line.right.key);
- break;
- }
- } else {
- ++count;
- res = temp.add(controlPoints.get(i).key, true);
- if (res != null) {
- finished = true;
- System.out.println("INTERSECTION");
- System.out.println(res);
- System.out.println(controlPoints.get(i).key);
- break;
- }
- }
- }
- if (!finished)
- System.out.println("NO INTERSECTIONS");
- }
- static public <T> boolean checkIntersection(T aT, T bT) {
- if (aT == null || bT == null)
- return false;
- Segment b = (Segment) aT, a = (Segment) bT;
- double denominator = (a.beginX - a.endX) * (b.beginY - b.endY) - (a.beginY - a.endY) * (b.beginX - b.endX);
- if (denominator == 0)
- return false;
- double x = (a.beginX * a.endY - a.beginY * a.endX) * (b.beginX - b.endX)
- - (b.beginX * b.endY - b.beginY * b.endX) * (a.beginX - a.endX);
- double y = (a.beginX * a.endY - a.beginY * a.endX) * (b.beginY - b.endY)
- - (b.beginX * b.endY - b.beginY * b.endX) * (a.beginY - a.endY);
- x /= denominator;
- y /= denominator;
- boolean checkArea = ((x > a.beginX && x < a.endX) || (x < a.beginX && x > a.endX))
- && ((y > a.beginY && y < a.endY) || (y < a.beginY && y > a.endY))
- && ((x > b.beginX && x < b.endX) || (x < b.beginX && x > b.endX))
- && ((y > b.beginY && y < b.endY) || (y < b.beginY && y > b.endY));
- return checkArea;
- }
- }
- class ControlPont implements Comparable<ControlPont> {
- public Long x;
- public Boolean begin;
- public Segment key;
- public ControlPont(Long x, boolean begin, Segment key) {
- this.x = x;
- this.begin = begin;
- this.key = key;
- }
- @Override
- public int compareTo(ControlPont o) {
- if (x.equals(o.x))
- if (this.begin)
- return -1;
- else if (o.begin)
- return 1;
- return x.compareTo(o.x);
- }
- }
- class Segment implements Comparable<Segment> {
- public Long beginX, beginY, endX, endY;
- public Segment(Long xBegin, Long yBegin, Long xEnd, Long yEnd) {
- this.beginX = xBegin;
- this.beginY = yBegin;
- this.endX = xEnd;
- this.endY = yEnd;
- }
- public String toString() {
- return Long.toString(beginX) + " " + Long.toString(beginY) + " " + Long.toString(endX) + " "
- + Long.toString(endY);
- }
- public boolean isEqual(Segment o) {
- return ((beginX.equals(o.beginX) && endX.equals(o.endX)) || (beginX.equals(o.endX) && endX.equals(o.beginX)))
- && ((beginX.equals(o.beginX) && endX.equals(o.endX))
- || (beginX.equals(o.endX) && endX.equals(o.beginX)));
- }
- @Override
- public int compareTo(Segment o) {
- return beginY.compareTo(o.beginY);
- }
- }
- class MergeSort<T> implements Comparable<T> {
- @SuppressWarnings("unchecked")
- public static <T> T[] mergeSort(T[] array, int left, int right) {
- if (left == right)
- return array;
- int mid = (left + right) / 2;
- mergeSort(array, left, mid);
- mergeSort(array, mid + 1, right);
- int i = left, j = mid + 1;
- T[] temp = Arrays.copyOf(array, right - left + 1);
- for (int k = 0; k < temp.length; k++) {
- if (i > mid)
- temp[k] = array[j++];
- else if (j > right)
- temp[k] = array[i++];
- else if (((Comparable<T>) array[i]).compareTo(array[j]) > 0)
- temp[k] = array[j++];
- else
- temp[k] = array[i++];
- }
- for (int k = 0; k < temp.length; k++)
- array[k + left] = temp[k];
- return array;
- }
- @Override
- public int compareTo(T o) {
- return this.compareTo(o);
- }
- }
- class AVL_Tree<T> implements Comparable<T> {
- private Node<T> top;
- public static int nodeHeight(Node<?> node) {
- if (node == null)
- return 0;
- return node.height;
- }
- public static int balanceFactor(Node<?> node) {
- if (node == null)
- return 0;
- return nodeHeight(node.left) - nodeHeight(node.right);
- }
- public static void calculateNodeHeight(Node<?> node) {
- if (nodeHeight(node.left) > nodeHeight(node.right))
- node.height = nodeHeight(node.left) + 1;
- else
- node.height = nodeHeight(node.right) + 1;
- }
- public void add(T key) {
- top = add(top, key);
- }
- public Segment add(T key, boolean find) {
- Sweep_line.right = null;
- Sweep_line.left = null;
- add(key);
- if (Sweep_line.right != null && Sweep_line.checkIntersection(key, Sweep_line.right.key))
- return Sweep_line.right.key;
- if (Sweep_line.left != null && Sweep_line.checkIntersection(key, Sweep_line.left.key))
- return Sweep_line.left.key;
- return null;
- }
- @SuppressWarnings("unchecked")
- private Node<T> add(Node<T> node, T key) {
- if (node == null) {
- return new Node<T>(key);
- }
- if (((Comparable<T>) key).compareTo(node.key) < 0) {
- Sweep_line.right = (Node<Segment>) node;
- node.left = add(node.left, key);
- } else {
- Sweep_line.left = (Node<Segment>) node;
- node.right = add(node.right, key);
- }
- node.height = 1
- + (nodeHeight(node.left) > nodeHeight(node.right) ? nodeHeight(node.left) : nodeHeight(node.right));
- return nodeBalancing(node);
- }
- public boolean remove(T key) {
- Sweep_line.left = null;
- Sweep_line.right = null;
- top = remove(top, key);
- if (Sweep_line.right != null && Sweep_line.left != null
- && Sweep_line.checkIntersection(Sweep_line.left.key, Sweep_line.right.key))
- return true;
- return false;
- }
- @SuppressWarnings("unchecked")
- private Node<T> remove(Node<T> node, T key) {
- if (node == null)
- return node;
- if (((Comparable<T>) key).compareTo(node.key) < 0) {
- Sweep_line.right = (Node<Segment>) node;
- node.left = remove(node.left, key);
- } else if (((Comparable<T>) key).compareTo(node.key) > 0) {
- Sweep_line.left = (Node<Segment>) node;
- node.right = remove(node.right, key);
- } else {
- Node<T> tempLeft = node.left, tempRight = node.right;
- while (tempLeft != null && tempLeft.right != null)
- tempLeft = tempLeft.right;
- while (tempRight != null && tempRight.left != null)
- tempRight = tempRight.left;
- if (tempLeft != null)
- Sweep_line.left = (Node<Segment>) tempLeft;
- if (tempRight != null)
- Sweep_line.right = (Node<Segment>) tempRight;
- if (node.left == null && node.right == null)
- return null;
- if (node.left == null) {
- Node<T> temp = node.right;
- node = null;
- return temp;
- }
- if (node.right == null) {
- Node<T> temp = node.left;
- node = null;
- return temp;
- }
- Node<T> temp = node.left;
- while (temp != null && temp.right != null)
- temp = temp.right;
- node.key = temp.key;
- node.left = remove(node.left, temp.key);
- }
- calculateNodeHeight(node);
- return nodeBalancing(node);
- }
- private Node<T> nodeBalancing(Node<T> node) {
- int balance = balanceFactor(node);
- if (balance > 1) {
- if (balanceFactor(node.left) < 0) {
- node.left = leftRotation(node.left);
- }
- return rightRotation(node);
- }
- if (balance < -1) {
- if (balanceFactor(node.right) > 0) {
- node.right = rightRotation(node.right);
- }
- return leftRotation(node);
- }
- return node;
- }
- private Node<T> rightRotation(Node<T> node) {
- Node<T> temp = node.left;
- node.left = temp.right;
- temp.right = node;
- calculateNodeHeight(node);
- calculateNodeHeight(temp);
- return temp;
- }
- private Node<T> leftRotation(Node<T> node) {
- Node<T> temp = node.right;
- node.right = temp.left;
- temp.left = node;
- calculateNodeHeight(node);
- calculateNodeHeight(temp);
- return temp;
- }
- @Override
- public int compareTo(T o) {
- return this.compareTo(o);
- }
- }
- class Node<T> implements Comparable<T> {
- public T key;
- public Node<T> left, right;
- public int height;
- Node(T key) {
- this.key = key;
- left = null;
- right = null;
- height = 1;
- }
- Node(Node<T> node) {
- this.key = node.key;
- this.left = node.left;
- this.right = node.right;
- }
- @Override
- public int compareTo(T o) {
- this.compareTo(o);
- return 0;
- }
- }
- class Scanner {
- InputStream in;
- char c;
- Scanner(InputStream in) {
- this.in = in;
- nextChar();
- }
- void asserT(boolean e) {
- if (!e) {
- throw new Error();
- }
- }
- void nextChar() {
- try {
- c = (char)in.read();
- } catch (IOException e) {
- throw new Error(e);
- }
- }
- long nextLong() {
- while (true) {
- if ('0' <= c && c <= '9' || c == '-') {
- break;
- }
- asserT(c != -1);
- nextChar();
- }
- long sign=1;
- if(c == '-'){
- sign=-1;
- nextChar();
- }
- long value = c - '0';
- nextChar();
- while ('0' <= c && c <= '9') {
- value *= 10;
- value += c - '0';
- nextChar();
- }
- value*=sign;
- return value;
- }
- int nextInt() {
- long longValue = nextLong();
- int intValue = (int)longValue;
- asserT(intValue == longValue);
- return intValue;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement