fork(11) download
  1. using System;
  2. using System.Drawing;
  3.  
  4. public class Test
  5. {
  6. public static void Main()
  7. {
  8. Console.WriteLine(LinesIntersect("0,0-2,8:8,0-0,20")); // No intersect
  9.  
  10. Console.WriteLine(LinesIntersect("0,10-2,0:10,0-0,5")); // Intersect
  11.  
  12. Console.WriteLine(LinesIntersect("0,0-0,10:2,0-2,10")); // Parallel, vertical
  13. Console.WriteLine(LinesIntersect("0,0-5,5:2,0-7,5")); // Parallel, diagonal
  14.  
  15. Console.WriteLine(LinesIntersect("0,0-5,5:2,2-7,7")); // Collinear, overlap
  16. Console.WriteLine(LinesIntersect("0,0-5,5:7,7-10,10")); // Collinear, no overlap
  17.  
  18. }
  19.  
  20. // Utility wrapper around LinesIntersect, expecting a string in the form:
  21. // A-B:C-D
  22. // Where A, B, C and D are cartesian coordinates in the form:
  23. // XX.XX,YY.YY
  24. static bool LinesIntersect(string s)
  25. {
  26. PointF A, B, C, D;
  27.  
  28. string[] split = s.Split(',', '-', ':');
  29.  
  30. A = new PointF(float.Parse(split[0]), float.Parse(split[1]));
  31. B = new PointF(float.Parse(split[2]), float.Parse(split[3]));
  32. C = new PointF(float.Parse(split[4]), float.Parse(split[5]));
  33. D = new PointF(float.Parse(split[6]), float.Parse(split[7]));
  34.  
  35. return LinesIntersect(A, B, C, D);
  36. }
  37.  
  38. // Determines if the lines AB and CD intersect.
  39. static bool LinesIntersect(PointF A, PointF B, PointF C, PointF D)
  40. {
  41. PointF CmP = new PointF(C.X - A.X, C.Y - A.Y);
  42. PointF r = new PointF(B.X - A.X, B.Y - A.Y);
  43. PointF s = new PointF(D.X - C.X, D.Y - C.Y);
  44.  
  45. float CmPxr = CmP.X * r.Y - CmP.Y * r.X;
  46. float CmPxs = CmP.X * s.Y - CmP.Y * s.X;
  47. float rxs = r.X * s.Y - r.Y * s.X;
  48.  
  49. if (CmPxr == 0f)
  50. {
  51. // Lines are collinear, and so intersect if they have any overlap
  52.  
  53. return ((C.X - A.X < 0f) != (C.X - B.X < 0f))
  54. || ((C.Y - A.Y < 0f) != (C.Y - B.Y < 0f));
  55. }
  56.  
  57. if (rxs == 0f)
  58. return false; // Lines are parallel.
  59.  
  60. float rxsr = 1f / rxs;
  61. float t = CmPxs * rxsr;
  62. float u = CmPxr * rxsr;
  63.  
  64. return (t >= 0f) && (t <= 1f) && (u >= 0f) && (u <= 1f);
  65. }
  66. }
Success #stdin #stdout 0.03s 33808KB
stdin
Standard input is empty
stdout
False
True
False
False
True
False