{"id":34022,"date":"2024-11-01T09:23:11","date_gmt":"2024-11-01T09:23:11","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34022"},"modified":"2024-11-01T10:53:58","modified_gmt":"2024-11-01T10:53:58","slug":"c-coding-test-course-finding-the-intersection-of-line-segments","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34022\/","title":{"rendered":"C# Coding Test Course, Finding the Intersection of Line Segments"},"content":{"rendered":"<article>\n<p>\n        Hello! In this post, we will discuss the coding test problem &#8216;Determining whether line segments intersect&#8217; using C#.<br \/>\n        This problem is a geometric problem, which determines whether the two given line segments intersect.<br \/>\n        It is a fundamental problem that is utilized in various fields, making it useful for improving algorithm problem-solving skills and mathematical reasoning.\n    <\/p>\n<h2>Problem Description<\/h2>\n<p>\n        Given line segment 1 with two points <code>A(x1, y1)<\/code> and <code>B(x2, y2)<\/code>, and line segment 2 with two points <code>C(x3, y3)<\/code> and <code>D(x4, y4)<\/code>,<br \/>\n        write a program to determine whether the two segments intersect.\n    <\/p>\n<h3>Input<\/h3>\n<ul>\n<li>Coordinates of the two points A and B of the first segment: <code>(x1, y1), (x2, y2)<\/code><\/li>\n<li>Coordinates of the two points C and D of the second segment: <code>(x3, y3), (x4, y4)<\/code><\/li>\n<\/ul>\n<h3>Output<\/h3>\n<p>\n        Output <code>true<\/code> if the two segments intersect, otherwise output <code>false<\/code>.\n    <\/p>\n<h2>Approach to Solution<\/h2>\n<p>\n        To solve this problem, it is necessary to understand the position relationships of the segments. For the segments to intersect, both of the following conditions must be satisfied:\n    <\/p>\n<ol>\n<li>The endpoints of segment AB must lie on opposite sides of segment CD.<\/li>\n<li>The endpoints of segment CD must lie on opposite sides of segment AB.<\/li>\n<\/ol>\n<h3>Mathematical Background<\/h3>\n<p>\n        Given the points, we can determine if two points are on opposite sides using the cross product of the vectors.<br \/>\n        If the signs of the cross product of the two vectors <code>v1 = B - A<\/code> and <code>v2 = C - A<\/code> are different, it means point C is on one side of segment AB,<br \/>\n        and point D is on the opposite side. This method can be used to determine the intersection of the segments.\n    <\/p>\n<h3>Implementation Method<\/h3>\n<p>\n        The basic logic to solve the problem is as follows:\n    <\/p>\n<ol>\n<li>Define the direction of each segment using the four given points A, B, C, and D.<\/li>\n<li>Create a cross product function to calculate the cross product of the two vectors.<\/li>\n<li>Compare the signs of the cross product based on the two cases and return whether they intersect.<\/li>\n<\/ol>\n<h2>C# Code Implementation<\/h2>\n<pre><code class=\"language-csharp\">\nusing System;\n\nclass Program\n{\n    static void Main()\n    {\n        \/\/ Input coordinates of points A, B, C, D\n        int[] A = { 1, 1 }; \/\/ (x1, y1)\n        int[] B = { 4, 4 }; \/\/ (x2, y2)\n        int[] C = { 1, 4 }; \/\/ (x3, y3)\n        int[] D = { 4, 1 }; \/\/ (x4, y4)\n\n        \/\/ Check intersection\n        bool isCross = DoSegmentsIntersect(A, B, C, D);\n        Console.WriteLine(isCross ? \"true\" : \"false\");\n    }\n\n    static bool DoSegmentsIntersect(int[] A, int[] B, int[] C, int[] D)\n    {\n        \/\/ Check intersection using cross product\n        int d1 = CrossProduct(A, B, C);\n        int d2 = CrossProduct(A, B, D);\n        int d3 = CrossProduct(C, D, A);\n        int d4 = CrossProduct(C, D, B);\n\n        \/\/ Must be on opposite sides to intersect\n        if (d1 * d2 < 0 &#038;&#038; d3 * d4 < 0)\n            return true;\n\n        \/\/ Also consider the case where the segments touch at endpoints\n        if (d1 == 0 &#038;&#038; IsOnSegment(A, B, C)) return true;\n        if (d2 == 0 &#038;&#038; IsOnSegment(A, B, D)) return true;\n        if (d3 == 0 &#038;&#038; IsOnSegment(C, D, A)) return true;\n        if (d4 == 0 &#038;&#038; IsOnSegment(C, D, B)) return true;\n\n        return false;\n    }\n\n    static int CrossProduct(int[] A, int[] B, int[] C)\n    {\n        \/\/ Calculate cross product\n        return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]);\n    }\n\n    static bool IsOnSegment(int[] A, int[] B, int[] P)\n    {\n        \/\/ Check if point P lies on segment AB\n        return Math.Min(A[0], B[0]) <= P[0] &#038;&#038; P[0] <= Math.Max(A[0], B[0]) &#038;&#038;\n               Math.Min(A[1], B[1]) <= P[1] &#038;&#038; P[1] <= Math.Max(A[1], B[1]);\n    }\n}\n<\/code><\/pre>\n<h2>Code Explanation<\/h2>\n<p>\n        The above code can solve the line segment intersection problem. The detailed explanation of each function is as follows.\n    <\/p>\n<ul>\n<li><code>Main<\/code>: The entry point of the program, which sets the points of each segment and checks for intersection.<\/li>\n<li><code>DoSegmentsIntersect<\/code>: The core logic to determine whether the two segments intersect is implemented in this function.<\/li>\n<li><code>CrossProduct<\/code>: This function calculates the cross product using the given three points. The result of the cross product is used to determine the direction.<\/li>\n<li><code>IsOnSegment<\/code>: This function checks whether a specific point lies on the segment.<\/li>\n<\/ul>\n<h2>Test Cases<\/h2>\n<p>\n        To test the given code, several test cases can be considered.\n    <\/p>\n<table>\n<thead>\n<tr>\n<th>Test Number<\/th>\n<th>Point A<\/th>\n<th>Point B<\/th>\n<th>Point C<\/th>\n<th>Point D<\/th>\n<th>Expected Result<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>1<\/td>\n<td>(1, 1)<\/td>\n<td>(4, 4)<\/td>\n<td>(1, 4)<\/td>\n<td>(4, 1)<\/td>\n<td>true<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>(1, 1)<\/td>\n<td>(2, 2)<\/td>\n<td>(2, 1)<\/td>\n<td>(3, 1)<\/td>\n<td>false<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>(0, 0)<\/td>\n<td>(3, 3)<\/td>\n<td>(0, 3)<\/td>\n<td>(3, 0)<\/td>\n<td>true<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>(0, 0)<\/td>\n<td>(5, 5)<\/td>\n<td>(1, 1)<\/td>\n<td>(5, 5)<\/td>\n<td>true<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Conclusion<\/h2>\n<p>\n        In this article, we implemented an algorithm to determine whether line segments intersect using C#.<br \/>\n        Understanding geometric problems helps in grasping these problem-solving techniques and lays the foundation for learning advanced algorithms.<br \/>\n        Let\u2019s continue solving various algorithm problems together. Thank you!\n    <\/p>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Hello! In this post, we will discuss the coding test problem &#8216;Determining whether line segments intersect&#8217; using C#. This problem is a geometric problem, which determines whether the two given line segments intersect. It is a fundamental problem that is utilized in various fields, making it useful for improving algorithm problem-solving skills and mathematical reasoning. &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34022\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, Finding 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":[90],"tags":[],"class_list":["post-34022","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"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, Finding 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\/34022\/\" \/>\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, Finding the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this post, we will discuss the coding test problem &#8216;Determining whether line segments intersect&#8217; using C#. This problem is a geometric problem, which determines whether the two given line segments intersect. It is a fundamental problem that is utilized in various fields, making it useful for improving algorithm problem-solving skills and mathematical reasoning. &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, Finding the Intersection of Line Segments&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34022\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:23:11+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:53:58+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\/34022\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34022\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Finding the Intersection of Line Segments\",\"datePublished\":\"2024-11-01T09:23:11+00:00\",\"dateModified\":\"2024-11-01T10:53:58+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34022\/\"},\"wordCount\":470,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34022\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34022\/\",\"name\":\"C# Coding Test Course, Finding the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:23:11+00:00\",\"dateModified\":\"2024-11-01T10:53:58+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34022\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34022\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34022\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Finding 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, Finding 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\/34022\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Finding the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this post, we will discuss the coding test problem &#8216;Determining whether line segments intersect&#8217; using C#. This problem is a geometric problem, which determines whether the two given line segments intersect. It is a fundamental problem that is utilized in various fields, making it useful for improving algorithm problem-solving skills and mathematical reasoning. &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, Finding the Intersection of Line Segments\"","og_url":"https:\/\/atmokpo.com\/w\/34022\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:23:11+00:00","article_modified_time":"2024-11-01T10:53:58+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\/34022\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34022\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Finding the Intersection of Line Segments","datePublished":"2024-11-01T09:23:11+00:00","dateModified":"2024-11-01T10:53:58+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34022\/"},"wordCount":470,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34022\/","url":"https:\/\/atmokpo.com\/w\/34022\/","name":"C# Coding Test Course, Finding the Intersection of Line Segments - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:23:11+00:00","dateModified":"2024-11-01T10:53:58+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34022\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34022\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34022\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Finding 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\/34022","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=34022"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34022\/revisions"}],"predecessor-version":[{"id":34023,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34022\/revisions\/34023"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34022"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34022"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34022"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}