Lesnic

DSA 1

Mar 27th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.45 KB | None | 0 0
  1. import java.math.*;
  2. import java.util.*;
  3. // Gorozhankin Egor BS19-01
  4. public class A {
  5.     public static void main(String[] args) {
  6.         Scan scanner = new Scan(System.in);
  7.         Segment segment1 = new Segment(scanner.nextLong(), scanner.nextLong(), scanner.nextLong(), scanner.nextLong());
  8.         Segment segment2 = new Segment(scanner.nextLong(), scanner.nextLong(), scanner.nextLong(), scanner.nextLong());
  9.        
  10.         if (intersection(segment1, segment2)) {
  11.             System.out.println("INTERSECTION");
  12.             System.out.println(segment1);
  13.             System.out.println(segment2);
  14.         } else {
  15.             System.out.println("NO INTERSECTIONS");
  16.         }
  17.     }
  18.    
  19.     static public boolean intersection(Segment a, Segment b) { // find intersection of two line segments
  20.         double denominator = (a.begin.x - a.end.x) * (b.begin.y - b.end.y) - (a.begin.y - a.end.y) * (b.begin.x - b.end.x);
  21.         if (denominator == 0)
  22.             return false;
  23.         double x = (a.begin.x * a.end.y - a.begin.y * a.end.x) * (b.begin.x - b.end.x) - (b.begin.x * b.end.y - b.begin.y * b.end.x) * (a.begin.x - a.end.x);
  24.         double y = (a.begin.x * a.end.y - a.begin.y * a.end.x) * (b.begin.y - b.end.y) - (b.begin.x * b.end.y - b.begin.y * b.end.x) * (a.begin.y - a.end.y);
  25.         if (a.checkCoordinate(x, y) && b.checkCoordinate(x, y))
  26.             return true;
  27.         return false;
  28.     }
  29. }
  30.  
  31. class Coordinate{
  32.     public long x, y;
  33.     public Coordinate(Long x, Long y) {
  34.         this.x = x;
  35.         this.y = y;
  36.     }
  37.     public boolean isEqual(double x, double y) { // check whether two coordinates are equal
  38.         return x == this.x && y == this.y;
  39.     }
  40.     public String toString() { // prepare coordinate for output
  41.         return Double.toString(x) + " " + Double.toString(y);
  42.     }
  43. }
  44.  
  45. class Segment{
  46.     public Coordinate begin, end;
  47.    
  48.     public Segment(Long xBegin, Long yBegin, Long xEnd, Long yEnd){
  49.         begin = new Coordinate(xBegin, yBegin);
  50.         end = new Coordinate(xEnd, yEnd);
  51.     }
  52.    
  53.     public boolean checkCoordinate(double x, double y) { // check whether point of intersection belongs to line segment
  54.         boolean checkArea = ((x > begin.x && x < end.x) || (x < begin.x && x > end.x))
  55.                 && ((y > begin.y && y < end.y) || (y < begin.y && y > end.y))
  56.                 && ((x > begin.x && x < end.x) || (x < begin.x && x > end.x))
  57.                 && ((y > begin.y && y < end.y) || (y < begin.y && y > end.y));
  58.         boolean checkEndPoints = begin.isEqual(x, y) || end.isEqual(x, y);
  59.         return checkArea && !checkEndPoints;
  60.     }
  61.    
  62.     public String toString() { // prepare segment for output
  63.         return begin.toString() + " " + end.toString();
  64.     }
  65. }
Add Comment
Please, Sign In to add comment