D(x4, y4)<\/li>\n<\/ul>\nOutput Format<\/h2>\n
If the segments intersect, output “YES”; otherwise, output “NO”.<\/p>\n
Basic Theory for Problem Solving<\/h2>\n
One of the methods we can use to determine if segments intersect is a geometric approach. Specifically, we can use the cross product of vectors to ascertain whether the two segments cross each other.<\/p>\n
Cross Product<\/h3>\n
The cross product between two vectors AB(x2-x1, y2-y1) and AC(x3-x1, y3-y1) is defined as follows:<\/p>\n
\n Cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)\n <\/code><\/pre>\nThis value allows us to determine the direction of the two vectors. If the value of the cross product is 0, it means the vectors are collinear; a positive value indicates one direction, while a negative value indicates the opposite direction.<\/p>\n
Intersection Conditions for Line Segments<\/h2>\n
To determine if two segments AB and CD intersect, we need to check the following conditions:<\/p>\n
\n- When the two segments are in the “general case” (the endpoints of AB and CD are in different directions)<\/li>\n
- When the two segments “meet at a single point” (intersecting at an internal point)<\/li>\n
- When the two segments “meet at an endpoint” (an endpoint of one segment is on the other segment)<\/li>\n<\/ol>\n
General Case<\/h3>\n
To confirm that segments AB and CD are in different directions, we compare the signs of the cross products using the points A, B and C, and A, B and D. If the two segments are in different directions, these two signs must be different.<\/p>\n
Single\/Endpoint Meeting Cases<\/h3>\n
Unlike the general case, to judge if they meet at a point rather than crossing, we need to check if the endpoints of the segments are on each other’s segments.<\/p>\n
Python Code Implementation<\/h2>\n
Based on the basic theory above, we can write the following Python code.<\/p>\n
\ndef orientation(px, py, qx, qy, rx, ry):\n val = (qy - py) * (rx - qx) - (qx - px) * (ry - qy)\n if val == 0: return 0 # Collinear\n return 1 if val > 0 else 2 # Clockwise or Counterclockwise\n\ndef on_segment(px, py, qx, qy, rx, ry):\n return min(px, qx) <= rx <= max(px, qx) and min(py, qy) <= ry <= max(py, qy)\n\ndef do_intersect(p1, q1, p2, q2):\n o1 = orientation(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1])\n o2 = orientation(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1])\n o3 = orientation(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1])\n o4 = orientation(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1])\n\n if o1 != o2 and o3 != o4:\n return True\n \n if o1 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1]):\n return True\n\n if o2 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1]):\n return True\n\n if o3 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1]):\n return True\n\n if o4 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1]):\n return True\n\n return False\n\n# Test case\nA = (0, 0)\nB = (10, 10)\nC = (0, 10)\nD = (10, 0)\n\nif do_intersect(A, B, C, D):\n print(\"YES\")\nelse:\n print(\"NO\")\n <\/code><\/pre>\nCode Explanation and Test Cases<\/h2>\n
In the above code, the orientation function first determines the relative position of three points. The on_segment function checks if a point lies on a given segment. The do_intersect function determines whether two segments intersect. At the end of the code, the actual test case allows us to verify the results.<\/p>\n
Conclusion<\/h2>\n
In this lecture, we explored various theoretical backgrounds and Python code implementations to solve the problem of \"Determining if Line Segments Intersect.\" I hope this has provided an opportunity to enhance both your geometric thinking and programming skills while working through a specific algorithm problem. I wish for your continued growth in coding abilities!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
You are now going to take a closer look at one of the algorithm problems, “Determining if Line Segments Intersect.” In this lecture, we will explain the theory and actual implementation process step by step to solve this problem. It will be very beneficial for those who want to improve their algorithm problem-solving skills. Problem … \ub354 \ubcf4\uae30 “Python Coding Test Course, Determining the Intersection of Line Segments”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[145],"tags":[],"class_list":["post-33668","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"\nPython Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33668\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Python Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"You are now going to take a closer look at one of the algorithm problems, “Determining if Line Segments Intersect.” In this lecture, we will explain the theory and actual implementation process step by step to solve this problem. It will be very beneficial for those who want to improve their algorithm problem-solving skills. Problem … \ub354 \ubcf4\uae30 "Python Coding Test Course, Determining the Intersection of Line Segments"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33668\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:19:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:47:12+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Python Coding Test Course, Determining the Intersection of Line Segments\",\"datePublished\":\"2024-11-01T09:19:09+00:00\",\"dateModified\":\"2024-11-01T11:47:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/\"},\"wordCount\":550,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33668\/\",\"name\":\"Python Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:19:09+00:00\",\"dateModified\":\"2024-11-01T11:47:12+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33668\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33668\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Python Coding Test Course, Determining the Intersection of Line Segments\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Python Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33668\/","og_locale":"ko_KR","og_type":"article","og_title":"Python Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"You are now going to take a closer look at one of the algorithm problems, “Determining if Line Segments Intersect.” In this lecture, we will explain the theory and actual implementation process step by step to solve this problem. It will be very beneficial for those who want to improve their algorithm problem-solving skills. Problem … \ub354 \ubcf4\uae30 \"Python Coding Test Course, Determining the Intersection of Line Segments\"","og_url":"https:\/\/atmokpo.com\/w\/33668\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:19:09+00:00","article_modified_time":"2024-11-01T11:47:12+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33668\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33668\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Python Coding Test Course, Determining the Intersection of Line Segments","datePublished":"2024-11-01T09:19:09+00:00","dateModified":"2024-11-01T11:47:12+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33668\/"},"wordCount":550,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33668\/","url":"https:\/\/atmokpo.com\/w\/33668\/","name":"Python Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:19:09+00:00","dateModified":"2024-11-01T11:47:12+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33668\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33668\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33668\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Python Coding Test Course, Determining the Intersection of Line Segments"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33668","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33668"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33668\/revisions"}],"predecessor-version":[{"id":33669,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33668\/revisions\/33669"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}