PointInPolygon

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
#define eps 1e-9

class PointInPolygon
{
public:
    string testPoint(vector <string>, int, int);
};

struct point
{
    int x,y;
};

bool isOnSeg(point a,point b,point c)
{
    int minx=min(a.x,b.x);
    int maxx=max(a.x,b.x);
    int miny=min(a.y,b.y);
    int maxy=max(a.y,b.y);
    return (c.x>=minx and c.x<=maxx and c.y>=miny and c.y<=maxy);
}

int orientation(point a,point b,point c)
{
    /// By slope formula...
    int delta=(c.x-b.x)*(b.y-a.y)-(b.x-a.x)*(c.y-b.y);
    if(delta==0) return 0;
    if(delta<0) return -1;
    return +1;
}

bool is_Segment_Segment_Intersection(point a,point b,point c,point d)
{
    int o1=orientation(a,b,c);
    int o2=orientation(a,b,d);
    int o3=orientation(c,d,a);
    int o4=orientation(c,d,b);
    if(o1!=o2 and o3!=o4) return true;
    return false;
}

string PointInPolygon::testPoint(vector <string> vrt, int X, int Y)
{
    vector<point>v;
    int i,sz,cnt;
    stringstream ss;
    point pts,a,b,s,t;
    sz=vrt.size();
    for(i=0; i<sz; i++)
    {
        ss.str(vrt[i]);
        ss>>pts.x;
        ss>>pts.y;
        v.push_back(pts);
        ss.clear();
    }
    s.x=X;
    s.y=Y;
    t.x=700;
    t.y=Y;
    cnt=0;
    for(i=0; i<sz; i++)
    {
        a.x=v[i].x;
        a.y=v[i].y;
        b.x=v[(i+1)%sz].x;
        b.y=v[(i+1)%sz].y;
        if(isOnSeg(a,b,s)) return "BOUNDARY";
        if(is_Segment_Segment_Intersection(a,b,s,t)) ++cnt;
    }
    if(cnt&1) return "INTERIOR";
    return "EXTERIOR";
}