#ifndef INTAREACALCUTIL_H
#define INTAREACALCUTIL_H
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct Point
{
    Point(){}
    Point(int x1,int y1)
    {
        x=x1;
        y=y1;
    }
    int x;
    int y;
};
class IntAreaCalcUtil
{


public:
//若点a大于点b,即点a在点b顺时针方向,返回true,否则返回false
static bool PointCmp(const Point &a,const Point &b,const Point &center)
{
    if (a.x >= 0 && b.x < 0)
        return true;
    if (a.x == 0 && b.x == 0)
        return a.y > b.y;
    //向量OA和向量OB的叉积
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;
    //向量OA和向量OB共线，以距离判断大小
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.y) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}
static void ClockwiseSortPoints(std::vector<Point> &vPoints)
{
    //计算重心
    Point center;
    double x = 0,y = 0;
    for (int i = 0;i < vPoints.size();i++)
    {
        x += vPoints[i].x;
        y += vPoints[i].y;
    }
    center.x = (int)x/vPoints.size();
    center.y = (int)y/vPoints.size();

    //冒泡排序
    for(int i = 0;i < vPoints.size() - 1;i++)
    {
        for (int j = 0;j < vPoints.size() - i - 1;j++)
        {
            if (PointCmp(vPoints[j],vPoints[j+1],center))
            {
                Point tmp = vPoints[j];
                vPoints[j] = vPoints[j + 1];
                vPoints[j + 1] = tmp;
            }
        }
    }
}
//  The function will return YES if the point x,y is inside the polygon, or
//  NO if it is not.  If the point is exactly on the edge of the polygon,
//  then the function may return YES or NO.
static bool IsPointInPolygon(std::vector<Point> poly,Point pt)
{
    int i,j;
    bool c = false;
    for (i = 0,j = poly.size() - 1;i < poly.size();j = i++)
    {
        if ((((poly[i].y <= pt.y) && (pt.y < poly[j].y)) ||
            ((poly[j].y <= pt.y) && (pt.y < poly[i].y)))
            && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) + poly[i].x))
        {
            c = !c;
        }
    }
    return c;
}
//排斥实验
static bool IsRectCross(const Point &p1,const Point &p2,const Point &q1,const Point &q2)
{
    bool ret = min(p1.x,p2.x) <= max(q1.x,q2.x)    &&
                min(q1.x,q2.x) <= max(p1.x,p2.x) &&
                min(p1.y,p2.y) <= max(q1.y,q2.y) &&
                min(q1.y,q2.y) <= max(p1.y,p2.y);
    return ret;
}
//跨立判断
static bool IsLineSegmentCross(const Point &pFirst1,const Point &pFirst2,const Point &pSecond1,const Point &pSecond2)
{
    long line1,line2;
    line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
        pFirst2.x * (pFirst1.y - pSecond1.y) +
        pSecond1.x * (pFirst2.y - pFirst1.y);
    line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
        pFirst2.x * (pFirst1.y - pSecond2.y) +
        pSecond2.x * (pFirst2.y - pFirst1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
        return false;

    line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
        pSecond2.x * (pSecond1.y - pFirst1.y) +
        pFirst1.x * (pSecond2.y - pSecond1.y);
    line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
        pSecond2.x * (pSecond1.y - pFirst2.y) +
        pFirst2.x * (pSecond2.y - pSecond1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
        return false;
    return true;
}

static bool GetCrossPoint(const Point &p1,const Point &p2,const Point &q1,const Point &q2,long &x,long &y)
{
    if(IsRectCross(p1,p2,q1,q2))
    {
        if (IsLineSegmentCross(p1,p2,q1,q2))
        {
            //求交点
            long tmpLeft,tmpRight;
            tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
            tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);

            x = (int)((double)tmpRight/(double)tmpLeft);

            tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
            tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
            y = (int)((double)tmpRight/(double)tmpLeft);
            return true;
        }
    }
    return false;
}
static bool PolygonClip(const vector<Point> &poly1,const vector<Point> &poly2, std::vector<Point> &interPoly)
{
    if (poly1.size() < 3 || poly2.size() < 3)
    {
        return false;
    }

    long x,y;
    //计算多边形交点vector<Point> poly1;
    for (int i = 0;i < poly1.size();i++)
    {
        int poly1_next_idx = (i + 1) % poly1.size();
        for (int j = 0;j < poly2.size();j++)
        {
            int poly2_next_idx = (j + 1) % poly2.size();
            if (GetCrossPoint(poly1[i],poly1[poly1_next_idx],
                poly2[j],poly2[poly2_next_idx],
                x,y))
            {
                if(x<0 || y<0) continue;
                interPoly.push_back(Point(x,y));
            }
        }
    }

    //计算多边形内部点
    for(int i = 0;i < poly1.size();i++)
    {
        if (IsPointInPolygon(poly2,poly1[i]))
        {
            interPoly.push_back(poly1[i]);
        }
    }
    for (int i = 0;i < poly2.size();i++)
    {
        if (IsPointInPolygon(poly1,poly2[i]))
        {
            interPoly.push_back(poly2[i]);
        }
    }

    if(interPoly.size() <= 0)
        return false;

    //点集排序
    ClockwiseSortPoints(interPoly);
    return true;
}
static float intAreaCalc(vector<Point> &vecPoly)//求解多边形的面积(知道多边形的顶点，按顺时针或者逆时针)
{
    int  i_count=vecPoly.size();
   // iCycle=0;
    int area_temp=0;
    for(int i=0;i<i_count;i++)
    {
        area_temp=area_temp+(vecPoly[i].x*vecPoly[(i+1) % i_count].y-vecPoly[(i+1) % i_count].x*vecPoly[i].y);
    }
    return abs(area_temp*100/2);
}

//int main()
//{
//    vector<Point> poly1;
//    poly1.push_back(Point(1,0));
//    poly1.push_back(Point(1,2));
//    poly1.push_back(Point(3,0));
//  //  poly1.push_back(Point(1,2));
//    vector<Point> poly2;
////    poly2.push_back(Point(2,0));
////    poly2.push_back(Point(7,0));
////    poly2.push_back(Point(7,5));
////    poly2.push_back(Point(2,5));
//    poly2.push_back(Point(0,0));
//    poly2.push_back(Point(4,0));
//    poly2.push_back(Point(4,4));
//    poly2.push_back(Point(0,4));
//    vector<Point> poly3;
//    PolygonClip(poly1,poly2,poly3);
//    float inter = intAreaCalc(poly3);
//    float total = intAreaCalc(poly2);
//    int perset1 = (int)(inter / total * 100);
//    if(ALARM_PERCENT <= perset)
//    {

//    }




//    for(int i=0;i<poly3.size();++i)
//    {

//    }
//    return 0;
//}

};

#endif // INTAREACALCUTIL_H