{"id":34218,"date":"2024-11-01T09:25:39","date_gmt":"2024-11-01T09:25:39","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34218"},"modified":"2024-11-01T10:58:08","modified_gmt":"2024-11-01T10:58:08","slug":"c-coding-test-course-determining-the-intersection-of-line-segments","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34218\/","title":{"rendered":"C++ Coding Test Course, Determining the Intersection of Line Segments"},"content":{"rendered":"<article>\n<p>Hello, everyone preparing for the coding test! In this lecture, we will address the problem of determining whether two line segments intersect using C++. This problem is one of the geometric algorithm problems, which has various applications and is frequently presented in coding tests.<\/p>\n<h2>Problem Description<\/h2>\n<p>This is a problem of determining whether two given line segments intersect. Let&#8217;s assume line segment A is made up of two points P1(x1, y1) and P2(x2, y2), and line segment B is made up of two points P3(x3, y3) and P4(x4, y4). Our goal is to determine whether line segment A and line segment B intersect.<\/p>\n<h2>Input of the Problem<\/h2>\n<ul>\n<li>Coordinates of the endpoints P1 and P2 of the first line segment (x1, y1), (x2, y2)<\/li>\n<li>Coordinates of the endpoints P3 and P4 of the second line segment (x3, y3), (x4, y4)<\/li>\n<\/ul>\n<h2>Output of the Problem<\/h2>\n<p>If line segment A and line segment B intersect, output &#8220;1&#8221;; otherwise, output &#8220;0&#8221;.<\/p>\n<h2>Approach to the Problem<\/h2>\n<p>To determine the intersection of the line segments, we will utilize a geometric approach that allows us to easily determine if the given two segments intersect. Several cases need to be considered here:<\/p>\n<ol>\n<li>When the two segments are parallel<\/li>\n<li>When one segment blocks the other segment<\/li>\n<li>When the endpoints of the two segments are the same<\/li>\n<li>Contact between segments under certain conditions<\/li>\n<\/ol>\n<h2>Geometric Concepts<\/h2>\n<p>To determine whether the segments intersect, we will take a geometric approach using vectors. The equations of the two segments can be represented, and after converting them into vectors, we can determine if they intersect.<\/p>\n<p>Consider line segment A with points (x1, y1) and (x2, y2), and line segment B with points (x3, y3) and (x4, y4). Whether line segments A and B intersect can be easily determined through the positional relationship of the endpoints and the vectors.<\/p>\n<h3>Positional Relationship<\/h3>\n<p>We need to identify the direction of the vector <strong>AB<\/strong> connecting the two points of segment A and the vector <strong>CD<\/strong> connecting the two points of segment B. Generally, if these segments intersect, each point will be positioned in different directions.<\/p>\n<h3>Cross Product of Vectors<\/h3>\n<p>Using the cross product of vectors, we can compare the directions of the two vectors. Let\u2019s denote the two directional vectors of the segments as <strong>AB<\/strong> and <strong>AC<\/strong>. By calculating their cross product, we can determine the positional relationship of the two segments.<\/p>\n<h3>Mathematical Expression<\/h3>\n<p>The cross product of vectors can be expressed mathematically as follows:<\/p>\n<pre>\n    AB x AC = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)\n    <\/pre>\n<p>In this manner, we can calculate the cross product for each point to determine the direction of each segment. Depending on whether the result is positive, negative, or zero, we can differentiate between intersecting or parallel conditions.<\/p>\n<h2>C++ Code Implementation<\/h2>\n<p>Now, based on the theories discussed above, let&#8217;s write C++ code. This code will include logical operations to determine the positional relationships of the segments and check for intersection.<\/p>\n<pre><code>\n#include <iostream>\n\nusing namespace std;\n\nstruct Point {\n    int x, y;\n};\n\n\/\/ Function to check if two segments intersect\nbool doIntersect(Point p1, Point p2, Point p3, Point p4) {\n    \/\/ Calculate orientation\n    auto orientation = [](Point a, Point b, Point c) {\n        int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);\n        if (val == 0) return 0; \/\/ collinear\n        return (val > 0) ? 1 : 2; \/\/ clock or counterclockwise\n    };\n\n    int o1 = orientation(p1, p2, p3);\n    int o2 = orientation(p1, p2, p4);\n    int o3 = orientation(p3, p4, p1);\n    int o4 = orientation(p3, p4, p2);\n\n    \/\/ General case\n    if (o1 != o2 && o3 != o4)\n        return true;\n\n    \/\/ Special cases\n    \/\/ ...\n    return false;\n}\n\nint main() {\n    Point p1 = {1, 1}, p2 = {10, 1}, p3 = {1, 2}, p4 = {10, 2};\n    if (doIntersect(p1, p2, p3, p4)) {\n        cout << \"The segments intersect.\" << endl;\n    } else {\n        cout << \"The segments do not intersect.\" << endl;\n    }\n    return 0;\n}\n    <\/iostream><\/code><\/pre>\n<h3>Code Analysis<\/h3>\n<p>In the above code, we first defined two points using a structure (Point) and wrote the doIntersect function to check for segment intersection. This function computes the orientation of the given four points and uses it to determine if the segments intersect. By checking the combinations of each orientation, we can verify the different intersection conditions and return the final result.<\/p>\n<h3>Test Cases<\/h3>\n<p>To test the above code, various test cases can be used. Here are a few examples:<\/p>\n<pre><code>\n    \/\/ Intersection case\n    Point p1 = {0, 0}, p2 = {10, 10}, p3 = {0, 10}, p4 = {10, 0};\n    \/\/ Non-intersecting case\n    Point p1 = {1, 1}, p2 = {10, 1}, p3 = {1, 2}, p4 = {10, 2};\n    <\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>In this lecture, we explored the process of implementing an algorithm to determine the intersection of segments using C++. Geometric problems are often demanded topics in coding tests, so it is important to grasp the fundamental concepts of geometry. Through various examples and practice problems, you can deepen your understanding of the algorithm.<\/p>\n<h2>Additional Practice Problems<\/h2>\n<p>Try solving the problems below for practice:<\/p>\n<ol>\n<li>Write several test cases including both intersecting and non-intersecting cases<\/li>\n<li>Expand the code to consider cases where segments touch<\/li>\n<li>Determine the intersection of segments in three-dimensional space<\/li>\n<\/ol>\n<p>That concludes the C++ coding test lecture. We will continue to cover various algorithm problems in the future. Thank you!<\/p>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Hello, everyone preparing for the coding test! In this lecture, we will address the problem of determining whether two line segments intersect using C++. This problem is one of the geometric algorithm problems, which has various applications and is frequently presented in coding tests. Problem Description This is a problem of determining whether two given &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34218\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C++ Coding Test Course, Determining the Intersection of Line Segments&#8221;<\/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":[111],"tags":[],"class_list":["post-34218","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C++ 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\/34218\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, everyone preparing for the coding test! In this lecture, we will address the problem of determining whether two line segments intersect using C++. This problem is one of the geometric algorithm problems, which has various applications and is frequently presented in coding tests. Problem Description This is a problem of determining whether two given &hellip; \ub354 \ubcf4\uae30 &quot;C++ Coding Test Course, Determining the Intersection of Line Segments&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34218\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:25:39+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:08+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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Determining the Intersection of Line Segments\",\"datePublished\":\"2024-11-01T09:25:39+00:00\",\"dateModified\":\"2024-11-01T10:58:08+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/\"},\"wordCount\":682,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34218\/\",\"name\":\"C++ 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:25:39+00:00\",\"dateModified\":\"2024-11-01T10:58:08+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34218\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34218\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ 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":"C++ 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\/34218\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Determining the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, everyone preparing for the coding test! In this lecture, we will address the problem of determining whether two line segments intersect using C++. This problem is one of the geometric algorithm problems, which has various applications and is frequently presented in coding tests. Problem Description This is a problem of determining whether two given &hellip; \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Determining the Intersection of Line Segments\"","og_url":"https:\/\/atmokpo.com\/w\/34218\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:25:39+00:00","article_modified_time":"2024-11-01T10:58:08+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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34218\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34218\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Determining the Intersection of Line Segments","datePublished":"2024-11-01T09:25:39+00:00","dateModified":"2024-11-01T10:58:08+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34218\/"},"wordCount":682,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34218\/","url":"https:\/\/atmokpo.com\/w\/34218\/","name":"C++ 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:25:39+00:00","dateModified":"2024-11-01T10:58:08+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34218\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34218\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34218\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ 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\/34218","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=34218"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34218\/revisions"}],"predecessor-version":[{"id":34219,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34218\/revisions\/34219"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}