using System;
using System.Drawing;
public class Test
{
public static void Main()
{
Console.WriteLine(LinesIntersect("0,0-2,8:8,0-0,20")); // No intersect
Console.WriteLine(LinesIntersect("0,10-2,0:10,0-0,5")); // Intersect
Console.WriteLine(LinesIntersect("0,0-0,10:2,0-2,10")); // Parallel, vertical
Console.WriteLine(LinesIntersect("0,0-5,5:2,0-7,5")); // Parallel, diagonal
Console.WriteLine(LinesIntersect("0,0-5,5:2,2-7,7")); // Collinear, overlap
Console.WriteLine(LinesIntersect("0,0-5,5:7,7-10,10")); // Collinear, no overlap
}
// Utility wrapper around LinesIntersect, expecting a string in the form:
// A-B:C-D
// Where A, B, C and D are cartesian coordinates in the form:
// XX.XX,YY.YY
static bool LinesIntersect(string s)
{
PointF A, B, C, D;
string[] split = s.Split(',', '-', ':');
A = new PointF(float.Parse(split[0]), float.Parse(split[1]));
B = new PointF(float.Parse(split[2]), float.Parse(split[3]));
C = new PointF(float.Parse(split[4]), float.Parse(split[5]));
D = new PointF(float.Parse(split[6]), float.Parse(split[7]));
return LinesIntersect(A, B, C, D);
}
// Determines if the lines AB and CD intersect.
static bool LinesIntersect(PointF A, PointF B, PointF C, PointF D)
{
PointF CmP = new PointF(C.X - A.X, C.Y - A.Y);
PointF r = new PointF(B.X - A.X, B.Y - A.Y);
PointF s = new PointF(D.X - C.X, D.Y - C.Y);
float CmPxr = CmP.X * r.Y - CmP.Y * r.X;
float CmPxs = CmP.X * s.Y - CmP.Y * s.X;
float rxs = r.X * s.Y - r.Y * s.X;
if (CmPxr == 0f)
{
// Lines are collinear, and so intersect if they have any overlap
return ((C.X - A.X < 0f) != (C.X - B.X < 0f))
|| ((C.Y - A.Y < 0f) != (C.Y - B.Y < 0f));
}
if (rxs == 0f)
return false; // Lines are parallel.
float rxsr = 1f / rxs;
float t = CmPxs * rxsr;
float u = CmPxr * rxsr;
return (t >= 0f) && (t <= 1f) && (u >= 0f) && (u <= 1f);
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uRHJhd2luZzsKCnB1YmxpYyBjbGFzcyBUZXN0CnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBNYWluKCkKCXsKICAgIAlDb25zb2xlLldyaXRlTGluZShMaW5lc0ludGVyc2VjdCgiMCwwLTIsODo4LDAtMCwyMCIpKTsgLy8gTm8gaW50ZXJzZWN0CiAgICAgICAgCiAgICAJQ29uc29sZS5Xcml0ZUxpbmUoTGluZXNJbnRlcnNlY3QoIjAsMTAtMiwwOjEwLDAtMCw1IikpOyAvLyBJbnRlcnNlY3QKICAgICAgICAKICAgICAgICBDb25zb2xlLldyaXRlTGluZShMaW5lc0ludGVyc2VjdCgiMCwwLTAsMTA6MiwwLTIsMTAiKSk7IC8vIFBhcmFsbGVsLCB2ZXJ0aWNhbAogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKExpbmVzSW50ZXJzZWN0KCIwLDAtNSw1OjIsMC03LDUiKSk7IC8vIFBhcmFsbGVsLCBkaWFnb25hbAogICAgICAgIAogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKExpbmVzSW50ZXJzZWN0KCIwLDAtNSw1OjIsMi03LDciKSk7IC8vIENvbGxpbmVhciwgb3ZlcmxhcAogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKExpbmVzSW50ZXJzZWN0KCIwLDAtNSw1OjcsNy0xMCwxMCIpKTsgLy8gQ29sbGluZWFyLCBubyBvdmVybGFwCiAgICAgICAgCgl9CiAgICAKICAgIC8vIFV0aWxpdHkgd3JhcHBlciBhcm91bmQgTGluZXNJbnRlcnNlY3QsIGV4cGVjdGluZyBhIHN0cmluZyBpbiB0aGUgZm9ybToKICAgIC8vIEEtQjpDLUQKICAgIC8vIFdoZXJlIEEsIEIsIEMgYW5kIEQgYXJlIGNhcnRlc2lhbiBjb29yZGluYXRlcyBpbiB0aGUgZm9ybToKICAgIC8vIFhYLlhYLFlZLllZCiAgICBzdGF0aWMgYm9vbCBMaW5lc0ludGVyc2VjdChzdHJpbmcgcykKICAgIHsKICAgICAgICBQb2ludEYgQSwgQiwgQywgRDsKICAgICAgICAKICAgICAgICBzdHJpbmdbXSBzcGxpdCA9IHMuU3BsaXQoJywnLCAnLScsICc6Jyk7CiAgICAgICAgCiAgICAgICAgQSA9IG5ldyBQb2ludEYoZmxvYXQuUGFyc2Uoc3BsaXRbMF0pLCBmbG9hdC5QYXJzZShzcGxpdFsxXSkpOwogICAgICAgIEIgPSBuZXcgUG9pbnRGKGZsb2F0LlBhcnNlKHNwbGl0WzJdKSwgZmxvYXQuUGFyc2Uoc3BsaXRbM10pKTsKICAgICAgICBDID0gbmV3IFBvaW50RihmbG9hdC5QYXJzZShzcGxpdFs0XSksIGZsb2F0LlBhcnNlKHNwbGl0WzVdKSk7CiAgICAgICAgRCA9IG5ldyBQb2ludEYoZmxvYXQuUGFyc2Uoc3BsaXRbNl0pLCBmbG9hdC5QYXJzZShzcGxpdFs3XSkpOwogICAgICAgIAogICAgICAgIHJldHVybiBMaW5lc0ludGVyc2VjdChBLCBCLCBDLCBEKTsKICAgIH0KICAgIAogICAgLy8gRGV0ZXJtaW5lcyBpZiB0aGUgbGluZXMgQUIgYW5kIENEIGludGVyc2VjdC4KCXN0YXRpYyBib29sIExpbmVzSW50ZXJzZWN0KFBvaW50RiBBLCBQb2ludEYgQiwgUG9pbnRGIEMsIFBvaW50RiBEKQoJewoJCVBvaW50RiBDbVAgPSBuZXcgUG9pbnRGKEMuWCAtIEEuWCwgQy5ZIC0gQS5ZKTsKCQlQb2ludEYgciA9IG5ldyBQb2ludEYoQi5YIC0gQS5YLCBCLlkgLSBBLlkpOwoJCVBvaW50RiBzID0gbmV3IFBvaW50RihELlggLSBDLlgsIEQuWSAtIEMuWSk7CgoJCWZsb2F0IENtUHhyID0gQ21QLlggKiByLlkgLSBDbVAuWSAqIHIuWDsKCQlmbG9hdCBDbVB4cyA9IENtUC5YICogcy5ZIC0gQ21QLlkgKiBzLlg7CgkJZmxvYXQgcnhzID0gci5YICogcy5ZIC0gci5ZICogcy5YOwoKCQlpZiAoQ21QeHIgPT0gMGYpCgkJewoJCQkvLyBMaW5lcyBhcmUgY29sbGluZWFyLCBhbmQgc28gaW50ZXJzZWN0IGlmIHRoZXkgaGF2ZSBhbnkgb3ZlcmxhcAoKCQkJcmV0dXJuICgoQy5YIC0gQS5YIDwgMGYpICE9IChDLlggLSBCLlggPCAwZikpCgkJCQl8fCAoKEMuWSAtIEEuWSA8IDBmKSAhPSAoQy5ZIC0gQi5ZIDwgMGYpKTsKCQl9CgoJCWlmIChyeHMgPT0gMGYpCgkJCXJldHVybiBmYWxzZTsgLy8gTGluZXMgYXJlIHBhcmFsbGVsLgoKCQlmbG9hdCByeHNyID0gMWYgLyByeHM7CgkJZmxvYXQgdCA9IENtUHhzICogcnhzcjsKCQlmbG9hdCB1ID0gQ21QeHIgKiByeHNyOwoKCQlyZXR1cm4gKHQgPj0gMGYpICYmICh0IDw9IDFmKSAmJiAodSA+PSAwZikgJiYgKHUgPD0gMWYpOwoJfQp9