#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
};
struct line {
Point p1, p2;
};
bool onLine(line l1, Point p)
{
// Check whether p is on the line or not
if (p.x <= max(l1.p1.x, l1.p2.x)
&& p.x <= min(l1.p1.x, l1.p2.x)
&& (p.y <= max(l1.p1.y, l1.p2.y)
&& p.y <= min(l1.p1.y, l1.p2.y)))
return true;
return false;
}
int direction(Point a, Point b, Point c)
{
int val = (b.y - a.y) * (c.x - b.x)
- (b.x - a.x) * (c.y - b.y);
if (val == 0)
// Colinear
return 0;
else if (val < 0)
// Anti-clockwise direction
return 2;
// Clockwise direction
return 1;
}
bool isIntersect(line l1, line l2)
{
// Four direction for two lines and points of other line
int dir1 = direction(l1.p1, l1.p2, l2.p1);
int dir2 = direction(l1.p1, l1.p2, l2.p2);
int dir3 = direction(l2.p1, l2.p2, l1.p1);
int dir4 = direction(l2.p1, l2.p2, l1.p2);
// When intersecting
if (dir1 != dir2 && dir3 != dir4)
return true;
// When p2 of line2 are on the line1
if (dir1 == 0 && onLine(l1, l2.p1))
return true;
// When p1 of line2 are on the line1
if (dir2 == 0 && onLine(l1, l2.p2))
return true;
// When p2 of line1 are on the line2
if (dir3 == 0 && onLine(l2, l1.p1))
return true;
// When p1 of line1 are on the line2
if (dir4 == 0 && onLine(l2, l1.p2))
return true;
return false;
}
bool checkInside(Point poly[], int n, Point p)
{
// When polygon has less than 3 edge, it is not polygon
if (n < 3)
return false;
// Create a point at infinity, y is same as point p
line exline = { p, { 9999, p.y } };
int count = 0;
int i = 0;
do {
// Forming a line from two consecutive points of
// poly
line side = { poly[i], poly[(i + 1) % n] };
if (isIntersect(side, exline)) {
// If side is intersects exline
if (direction(side.p1, p, side.p2) == 0)
return onLine(side, p);
count++;
}
i = (i + 1) % n;
} while (i != 0);
// When count is odd
return count & 1;
}
// Driver code
int main()
{
Point polygon[]
= { { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } };
Point p = { 5, 3 };
int n = 4;
// Function call
if (checkInside(polygon, n, p))
cout << "Point is inside.";
else
cout << "Point is outside.";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKc3RydWN0IFBvaW50IHsKICAgIGludCB4LCB5Owp9OwogCnN0cnVjdCBsaW5lIHsKICAgIFBvaW50IHAxLCBwMjsKfTsKIApib29sIG9uTGluZShsaW5lIGwxLCBQb2ludCBwKQp7CiAgICAvLyBDaGVjayB3aGV0aGVyIHAgaXMgb24gdGhlIGxpbmUgb3Igbm90CiAgICBpZiAocC54IDw9IG1heChsMS5wMS54LCBsMS5wMi54KQogICAgICAgICYmIHAueCA8PSBtaW4obDEucDEueCwgbDEucDIueCkKICAgICAgICAmJiAocC55IDw9IG1heChsMS5wMS55LCBsMS5wMi55KQogICAgICAgICAgICAmJiBwLnkgPD0gbWluKGwxLnAxLnksIGwxLnAyLnkpKSkKICAgICAgICByZXR1cm4gdHJ1ZTsKIAogICAgcmV0dXJuIGZhbHNlOwp9CiAKaW50IGRpcmVjdGlvbihQb2ludCBhLCBQb2ludCBiLCBQb2ludCBjKQp7CiAgICBpbnQgdmFsID0gKGIueSAtIGEueSkgKiAoYy54IC0gYi54KQogICAgICAgICAgICAgIC0gKGIueCAtIGEueCkgKiAoYy55IC0gYi55KTsKIAogICAgaWYgKHZhbCA9PSAwKQogCiAgICAgICAgLy8gQ29saW5lYXIKICAgICAgICByZXR1cm4gMDsKIAogICAgZWxzZSBpZiAodmFsIDwgMCkKIAogICAgICAgIC8vIEFudGktY2xvY2t3aXNlIGRpcmVjdGlvbgogICAgICAgIHJldHVybiAyOwogCiAgICAvLyBDbG9ja3dpc2UgZGlyZWN0aW9uCiAgICByZXR1cm4gMTsKfQogCmJvb2wgaXNJbnRlcnNlY3QobGluZSBsMSwgbGluZSBsMikKewogICAgLy8gRm91ciBkaXJlY3Rpb24gZm9yIHR3byBsaW5lcyBhbmQgcG9pbnRzIG9mIG90aGVyIGxpbmUKICAgIGludCBkaXIxID0gZGlyZWN0aW9uKGwxLnAxLCBsMS5wMiwgbDIucDEpOwogICAgaW50IGRpcjIgPSBkaXJlY3Rpb24obDEucDEsIGwxLnAyLCBsMi5wMik7CiAgICBpbnQgZGlyMyA9IGRpcmVjdGlvbihsMi5wMSwgbDIucDIsIGwxLnAxKTsKICAgIGludCBkaXI0ID0gZGlyZWN0aW9uKGwyLnAxLCBsMi5wMiwgbDEucDIpOwogCiAgICAvLyBXaGVuIGludGVyc2VjdGluZwogICAgaWYgKGRpcjEgIT0gZGlyMiAmJiBkaXIzICE9IGRpcjQpCiAgICAgICAgcmV0dXJuIHRydWU7CiAKICAgIC8vIFdoZW4gcDIgb2YgbGluZTIgYXJlIG9uIHRoZSBsaW5lMQogICAgaWYgKGRpcjEgPT0gMCAmJiBvbkxpbmUobDEsIGwyLnAxKSkKICAgICAgICByZXR1cm4gdHJ1ZTsKIAogICAgLy8gV2hlbiBwMSBvZiBsaW5lMiBhcmUgb24gdGhlIGxpbmUxCiAgICBpZiAoZGlyMiA9PSAwICYmIG9uTGluZShsMSwgbDIucDIpKQogICAgICAgIHJldHVybiB0cnVlOwogCiAgICAvLyBXaGVuIHAyIG9mIGxpbmUxIGFyZSBvbiB0aGUgbGluZTIKICAgIGlmIChkaXIzID09IDAgJiYgb25MaW5lKGwyLCBsMS5wMSkpCiAgICAgICAgcmV0dXJuIHRydWU7CiAKICAgIC8vIFdoZW4gcDEgb2YgbGluZTEgYXJlIG9uIHRoZSBsaW5lMgogICAgaWYgKGRpcjQgPT0gMCAmJiBvbkxpbmUobDIsIGwxLnAyKSkKICAgICAgICByZXR1cm4gdHJ1ZTsKIAogICAgcmV0dXJuIGZhbHNlOwp9CiAKYm9vbCBjaGVja0luc2lkZShQb2ludCBwb2x5W10sIGludCBuLCBQb2ludCBwKQp7CiAKICAgIC8vIFdoZW4gcG9seWdvbiBoYXMgbGVzcyB0aGFuIDMgZWRnZSwgaXQgaXMgbm90IHBvbHlnb24KICAgIGlmIChuIDwgMykKICAgICAgICByZXR1cm4gZmFsc2U7CiAKICAgIC8vIENyZWF0ZSBhIHBvaW50IGF0IGluZmluaXR5LCB5IGlzIHNhbWUgYXMgcG9pbnQgcAogICAgbGluZSBleGxpbmUgPSB7IHAsIHsgOTk5OSwgcC55IH0gfTsKICAgIGludCBjb3VudCA9IDA7CiAgICBpbnQgaSA9IDA7CiAgICBkbyB7CiAKICAgICAgICAvLyBGb3JtaW5nIGEgbGluZSBmcm9tIHR3byBjb25zZWN1dGl2ZSBwb2ludHMgb2YKICAgICAgICAvLyBwb2x5CiAgICAgICAgbGluZSBzaWRlID0geyBwb2x5W2ldLCBwb2x5WyhpICsgMSkgJSBuXSB9OwogICAgICAgIGlmIChpc0ludGVyc2VjdChzaWRlLCBleGxpbmUpKSB7CiAKICAgICAgICAgICAgLy8gSWYgc2lkZSBpcyBpbnRlcnNlY3RzIGV4bGluZQogICAgICAgICAgICBpZiAoZGlyZWN0aW9uKHNpZGUucDEsIHAsIHNpZGUucDIpID09IDApCiAgICAgICAgICAgICAgICByZXR1cm4gb25MaW5lKHNpZGUsIHApOwogICAgICAgICAgICBjb3VudCsrOwogICAgICAgIH0KICAgICAgICBpID0gKGkgKyAxKSAlIG47CiAgICB9IHdoaWxlIChpICE9IDApOwogCiAgICAvLyBXaGVuIGNvdW50IGlzIG9kZAogICAgcmV0dXJuIGNvdW50ICYgMTsKfQogCi8vIERyaXZlciBjb2RlCmludCBtYWluKCkKewogICAgUG9pbnQgcG9seWdvbltdCiAgICAgICAgPSB7IHsgMCwgMCB9LCB7IDEwLCAwIH0sIHsgMTAsIDEwIH0sIHsgMCwgMTAgfSB9OwogICAgUG9pbnQgcCA9IHsgNSwgMyB9OwogICAgaW50IG4gPSA0OwogCiAgICAvLyBGdW5jdGlvbiBjYWxsCiAgICBpZiAoY2hlY2tJbnNpZGUocG9seWdvbiwgbiwgcCkpCiAgICAgICAgY291dCA8PCAiUG9pbnQgaXMgaW5zaWRlLiI7CiAgICBlbHNlCiAgICAgICAgY291dCA8PCAiUG9pbnQgaXMgb3V0c2lkZS4iOwogICAKICAgIHJldHVybiAwOwp9