#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string.h>
using namespace std;
struct Node{
    double x;
    double y;
};
typedef Node Point;
typedef Node Vec;

// 判断直线AB与直线CD是否相交
int checkLine_intersection(Point A, Point B, Point C, Point D)
{
    Vec AB = {B.x - A.x, B.y - A.y};
    Vec CD = {D.x - C.x, D.y - C.y};
    return AB.x * CD.y - AB.y * CD.x;   //向量叉乘为0，即平行或重合
}

// 判断直线AB与线段CD是否相交
int checkLineAndSegment_intersection(Point A, Point B, Point C, Point D)
{
    double fC = (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y);
    double fD = (D.y - A.y) * (A.x - B.x) - (D.x - A.x) * (A.y - B.y);
    if((fC > 0 && fD > 0) || (fC < 0 && fD < 0))    //如果C点和D点在直线AB的同侧，则返回0
        return 0;
    else
        return 1;
}

// 判断线段AB与线段CD是否相交
// 只需判断直线AB与线段CD是否相交和直线CD是否与线段AB相交即可
int checkSegment_intersection(Point A, Point B, Point C, Point D)
{
    if(checkLineAndSegment_intersection(A, B, C, D)\
        && checkLineAndSegment_intersection(C, D, A, B)){
            return 1;
        }
    return 0;
}

// 判断P点是否在线段AB上
int checkPointOnSegment(Point A, Point B, Point P)
{
    Vec AP = {P.x - A.x, P.y - A.y};
    Vec AB = {B.x - A.x, B.y - A.y};
    if(P.x >= min(A.x, B.x) && P.x <= max(A.x, B.x)\
        && P.y >= min(A.y, B.y) && P.y <= max(A.y, B.y)\
        && AP.x * AB.y == AB.x * AP.y){
            return 1;
        }
    return 0;
}

// 判断点P(x, y)是否在 任意多边形内部
int pnpoly(vector<Point>& vertexes, Point P)
{
    int cnt = vertexes.size(), i, j, c = 0;
    for(i = 0, j = cnt - 1; i < cnt; j = i++)
    {
        if(checkPointOnSegment(vertexes[i], vertexes[j], P))
            return 0;
        if((vertexes[i].y > P.y) != (vertexes[j].y > P.y) && \
            (P.x < (vertexes[j].x - vertexes[i].x) * (P.y - vertexes[i].y) / (vertexes[j].y - vertexes[i].y) + vertexes[i].x))
                c = !c;
    }
    return c;
}

//返回向量叉乘 u * v
double cross(Vec u, Vec v)
{
    return u.x * v.y - v.x * u.y;
}

// 计算两条直线AB, CD的交点, 如果两直线相交，结果给P， 返回1， 否则返回0
int calculateTwoLines_intersection(Point A, Point B, Point C, Point D, Point &P)
{
    if(!checkLine_intersection(A, B, C, D)) return 0;
    Vec v = {B.x - A.x, B.y - A.y}, w = {D.x - C.x, D.y - C.y};
    Vec u = {A.x - C.x, A.y - C.y};
    double t = cross(w, u) / cross(v, w);
    P = {A.x + v.x * t, A.y + v.y * t};
    return 1;
}

// 计算任意多边形面积
double calculatePolygonArea(vector<Point>& vertexes)
{
    int i, j, cnt = vertexes.size();
    double ans = 0;
    for(int i = 0; i < cnt; i++)
    {
        j = (i + 1) % cnt;
        ans += vertexes[i].x * vertexes[j].y - vertexes[i].y * vertexes[j].x;
    }
    ans /= 2;
    return (ans < 0? -ans: ans);
}

// 求两点之间距离
double calculateTwoPointsDistance(Point A, Point B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

// 求点P与直线的最短距离
// 方向向量为0向量时，返回-1
double calculatePointAndLineDistance(Point A, Vec v, Point P)
{
    if(v.x == 0 && v.y == 0)    return -1;  //无效方向向量
    Vec AP = {P.x - A.x, P.y - A.y};
    double t = calculateTwoPointsDistance({0, 0}, v);
    double ans = cross(AP, v) / t;
    return (ans < 0? -ans: ans);
}
/*********圆与直线相关***********/


int main()
{
    // printf("%d\n", checkPosition(make_pair(0, 0), make_pair(1, 1), make_pair(1, 2)));
    // printf("%d\n", checkPosition(make_pair(0, 0), make_pair(-1, -1), make_pair(1, 2)));
    // printf("%d\n", check(make_pair(1, 2), make_pair(0, 0), make_pair(2, 0), make_pair(3, 2)));
    // printf("%d\n", check(make_pair(1, 2), make_pair(0, 0), make_pair(2, 0), make_pair(0, 2)));
    printf("%d\n", checkSegment_intersection({0, 0}, {3, 1}, {2, 0}, {3, 0}));
    vector<Point> v1 = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
    vector<Point> v2 = {{-1, 0}, {0, 1}, {0, 0}, {1, 0}, {0, -1}};
    printf("%d\n", pnpoly(v1, {0, 0.5}));
    Point P;
    if(calculateTwoLines_intersection({0, 0}, {1, 1}, {0, 1}, {1, 0}, P)){
        printf("%lf %lf\n", P.x, P.y);
    }

    printf("%lf\n", calculatePolygonArea(v2));

    printf("%lf\n", calculatePointAndLineDistance({0, 0}, {1, 1}, {2, 0}));
    return 0;
}