fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Point {
  5.     int x, y;
  6. };
  7.  
  8. struct line {
  9.     Point p1, p2;
  10. };
  11.  
  12. bool onLine(line l1, Point p)
  13. {
  14.     // Check whether p is on the line or not
  15.     if (p.x <= max(l1.p1.x, l1.p2.x)
  16.         && p.x <= min(l1.p1.x, l1.p2.x)
  17.         && (p.y <= max(l1.p1.y, l1.p2.y)
  18.             && p.y <= min(l1.p1.y, l1.p2.y)))
  19.         return true;
  20.  
  21.     return false;
  22. }
  23.  
  24. int direction(Point a, Point b, Point c)
  25. {
  26.     int val = (b.y - a.y) * (c.x - b.x)
  27.               - (b.x - a.x) * (c.y - b.y);
  28.  
  29.     if (val == 0)
  30.  
  31.         // Colinear
  32.         return 0;
  33.  
  34.     else if (val < 0)
  35.  
  36.         // Anti-clockwise direction
  37.         return 2;
  38.  
  39.     // Clockwise direction
  40.     return 1;
  41. }
  42.  
  43. bool isIntersect(line l1, line l2)
  44. {
  45.     // Four direction for two lines and points of other line
  46.     int dir1 = direction(l1.p1, l1.p2, l2.p1);
  47.     int dir2 = direction(l1.p1, l1.p2, l2.p2);
  48.     int dir3 = direction(l2.p1, l2.p2, l1.p1);
  49.     int dir4 = direction(l2.p1, l2.p2, l1.p2);
  50.  
  51.     // When intersecting
  52.     if (dir1 != dir2 && dir3 != dir4)
  53.         return true;
  54.  
  55.     // When p2 of line2 are on the line1
  56.     if (dir1 == 0 && onLine(l1, l2.p1))
  57.         return true;
  58.  
  59.     // When p1 of line2 are on the line1
  60.     if (dir2 == 0 && onLine(l1, l2.p2))
  61.         return true;
  62.  
  63.     // When p2 of line1 are on the line2
  64.     if (dir3 == 0 && onLine(l2, l1.p1))
  65.         return true;
  66.  
  67.     // When p1 of line1 are on the line2
  68.     if (dir4 == 0 && onLine(l2, l1.p2))
  69.         return true;
  70.  
  71.     return false;
  72. }
  73.  
  74. bool checkInside(Point poly[], int n, Point p)
  75. {
  76.  
  77.     // When polygon has less than 3 edge, it is not polygon
  78.     if (n < 3)
  79.         return false;
  80.  
  81.     // Create a point at infinity, y is same as point p
  82.     line exline = { p, { 9999, p.y } };
  83.     int count = 0;
  84.     int i = 0;
  85.     do {
  86.  
  87.         // Forming a line from two consecutive points of
  88.         // poly
  89.         line side = { poly[i], poly[(i + 1) % n] };
  90.         if (isIntersect(side, exline)) {
  91.  
  92.             // If side is intersects exline
  93.             if (direction(side.p1, p, side.p2) == 0)
  94.                 return onLine(side, p);
  95.             count++;
  96.         }
  97.         i = (i + 1) % n;
  98.     } while (i != 0);
  99.  
  100.     // When count is odd
  101.     return count & 1;
  102. }
  103.  
  104. // Driver code
  105. int main()
  106. {
  107.     Point polygon[]
  108.         = { { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } };
  109.     Point p = { 5, 3 };
  110.     int n = 4;
  111.  
  112.     // Function call
  113.     if (checkInside(polygon, n, p))
  114.         cout << "Point is inside.";
  115.     else
  116.         cout << "Point is outside.";
  117.  
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Point is inside.
https://ideone.com/rHtHAw
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!