fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4. import java.math.*;
  5.  
  6. class Ideone
  7. {
  8. 	//check common interval existence
  9. 	public static boolean segmentsOverlap(long l1, long r1, long l2, long r2){
  10. 		//segments [l1, r1], [l2, r2] (segment borders may not be sorted)
  11. 		//there is an intersection iff segments are neither located 
  12. 		//this way [l1, r1] ... [l2, r2] nor this [l2, r2] ... [l1, r1]
  13. 		return !(Math.max(l2, r2) < Math.min(l1, r1) || Math.max(l1, r1) < Math.min(l2, r2));
  14. 	}
  15. 	public static int sign(long n){
  16. 		if(n < 0) return -1;
  17. 		if(n > 0) return 1;
  18. 		return 0;
  19. 	}
  20. 	public static boolean segmentsIntersect(long A, long tA, long B, long tB, long C, long tC, long D, long tD){
  21. 		//find out the equations of the lines segments lie on
  22. 		//if segments intersect, both endpoints of one are located at
  23. 		//different half-planes relatively to second line
  24. 		//a1*X + b1*tX + c1 == 0	//a2*X + b1*tX + c2 == 0
  25. 		long a1 = tA-tB;			long a2 = tC-tD;
  26. 		long b1 = B-A;				long b2 = D-C;
  27. 		long c1 = A*tB-B*tA;		long c2 = C*tD-D*tC;
  28. 		long r1 = a1*C+b1*tC+c1;	long r3 = a2*A+b2*tA+c2;
  29. 		long r2 = a1*D+b1*tD+c1;	long r4 = a2*B+b2*tB+c2;
  30. 		return sign(r1)*sign(r2) <= 0 && sign(r3)*sign(r4) <= 0;
  31. 	}
  32. 	public static void main (String[] args) throws java.lang.Exception
  33. 	{
  34. 		Scanner in = new Scanner(System.in);
  35. 		long A = in.nextLong(); long tA = in.nextLong();
  36. 		long B = in.nextLong();	long tB = in.nextLong();
  37. 		long C = in.nextLong(); long tC = in.nextLong();
  38. 		long D = in.nextLong(); long tD = in.nextLong();
  39. 		if(segmentsOverlap(A, B, C, D) == true){
  40. 			//bots dots either lie in different half-planes or
  41. 			//at least one of them lies on the segment
  42. 			boolean r1 = segmentsIntersect(A, tA, B, tB, C, tC, D, tD);		//[(A,tA), (B,tB)] and [(C, tC), (D, tD)]
  43. 			boolean r2 = segmentsIntersect(A, tA, B, tB, C, 0, C, tC);		//[(A,tA), (B,tB)] and [(C, 0), (C, tC)]
  44. 			boolean r3 = segmentsIntersect(A, tA, B, tB, D, tD, D, tD+tB);	//[(A,tA), (B,tB)] and [(D, tD), (D, tD+tB)]
  45. 			boolean r4 = segmentsIntersect(C, tC, D, tD, A, 0, A, tA);		//[(C,tC), (D,tD)] and [(A, 0), (A, tA)]
  46. 			boolean r5 = segmentsIntersect(C, tC, D, tD, B, tB, B, tB+tD);  //[(C,tC), (D,tD)] and [(B, tB), (B, tB+tD)]
  47. 			if(r1 || r2 || r3 || r4 || r5)
  48. 				System.out.println("Yes");
  49. 			else 
  50. 				System.out.println("No");
  51. 		}
  52. 	}
  53. }
Success #stdin #stdout 0.14s 321344KB
comments (?)
stdin
copy 
0 0 
10 10
0 10
10 0
stdout
copy 
Yes
https://ideone.com/AxLzPh
WoW2
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!