点和线段的定义

1
2
3
4
5
6
7
8
typedef struct point {
    int x;
    int y;
}Point;
typedef struct segment {
    Point p1;
    Point p2;
}Segment;

叉积

叉积为正，p1位于p2顺时针方向，为负，p1位于p2逆时针方向
确定两个有向线段的顺逆时针方向，将有向线段源点都转化为原点，从而比较两个点的顺逆时针方向

1
2
3
long long CrossProduct(Point p1,Point p2){
    return p1.x*p2.y-p1.y*p2.x;
}

线段相交

两个连续线段的左转右转问题，同样可以看叉积确定顺逆时针，pi-》pj-》pk
负数就是逆时针，正数就是顺时针

1
2
3
long long Direction(Point pi,Point pj,Point pk){
    return (pk.x-pi.x)*(pj.y-pi.y)-(pk.y-pi.y)*(pj.x-pi.x);
}

两条线段相交的情况：

  1. 两条线段都跨越了对方所在直线
  2. 或者一条线段的某个端点在另一条直线上（特殊情况）
    返回1就是在线段上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int OnSegment(Point pi,Point pj,Point pk){//pk在不在线段pi，pj上
    if(min(pi.x,pj.x)<=pk.x&&pk.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=pk.y&&pk.y<=max(pi.y,pj.y))return 1;
    else return 0;
}
int SegmentIsIntersect(Point p1,Point p2,Point p3,Point p4){
    long long d1 = Direction(p3,p4,p1);
    long long d2 = Direction(p3,p4,p2);
    long long d3 = Direction(p1,p2,p3);
    long long d4 = Direction(p1,p2,p4);
    if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3<0&&d4>0)||(d3>0&&d4<0))){
        return 1;
    }
    else if(d1==0&&OnSegment(p3,p4,p1))return 1;
    else if(d2==0&&OnSegment(p3,p4,p2))return 1;
    else if(d3==0&&OnSegment(p1,p2,p3))return 1;
    else if(d4==0&&OnSegment(p1,p2,p4))return 1;
    else return 0;
}

点到线段的距离

包含了特殊情况

1
2
3
4
5
6
7
8
9
10
long double PointToSegment(Point p0, Point p1, Point p2) {
    long long cross = (p2.x - p1.x) * (p0.x - p1.x) + (p2.y - p1.y) * (p0.y - p1.y);
    if (cross <= 0)return sqrt((p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y));
    long long d2 = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
    if (cross >= d2)return sqrt((p0.x - p2.x) * (p0.x - p2.x) + (p0.y - p2.y) * (p0.y - p2.y));
    long double r = (long double) cross / d2;
    long double px = p1.x + (p2.x - p1.x) * r;
    long double py = p1.y + (p2.y - p1.y) * r;
    return sqrt((p0.x - px) * (p0.x - px) + (p0.y - py) * (p0.y - py));
}

Graham凸包

首先找到y坐标最小，最靠左的点p0，p0一定是凸包上的点

对p0参考，对其它所有点排序（根据幅角，或者是余弦值）

入栈p0，p1，p2，每次看一个点相对于栈顶两个元素连线的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Point p0;
Point stack[10000];
int top = -1;
long double Distance(Point p1,Point p2){
    return sqrtl((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
long long Direction(Point pi,Point pj,Point pk){
    return (pk.x-pi.x)*(pj.y-pi.y)-(pk.y-pi.y)*(pj.x-pi.x);
}
long long area(Point p0, Point p1, Point p2) {//这里算的是三角形面积的两倍
    return llabs((p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x));
}
int cmp(const void *e1,const void *e2){
    Point p1 = *((Point *)e1);
    Point p2 = *((Point *)e2);
    //计算相对点的余弦，余弦越小，幅角越大
    //这里让两个数同时乘以分母，避免除法
    long double f1 = (p1.x-p0.x)* Distance(p2,p0);
    long double f2 = (p2.x-p0.x)* Distance(p1,p0);
    if(fabsl(f1-f2)<1e-5){
        if(p1.x>p2.x)return 1;
        else if(p1.x<p2.x)return -1;
        else return 0;
    }
    else if(f1>f2)return -1;
    else if(f1<f2)return 1;
}
void GrahamScan(Point Q[],int n){
    top = -1;
    p0 = (Point){MAX,MAX};
    for(int i=0;i<n;i++){
        if(Q[i].y<p0.y)p0 = Q[i];
        else if(Q[i].y==p0.y){
            if(Q[i].x<p0.x)p0=Q[i];
        }
    }
    //p0为y坐标最小，如果y有一样的，p0就是最左边的那个
    for(int i=0;i<n;i++){//去除p0
        if(Q[i].x==p0.x&&Q[i].y==p0.y){
            for(;i<n-1;i++){
                Q[i]=Q[i+1];
            }
        }
    }
    qsort(Q,n-1,sizeof(Q[0]),cmp);
    stack[++top]=p0;
    stack[++top]=Q[0];
    if (n - 1 < 2)return;
    stack[++top]=Q[1];
    for(int i=2;i<n-1;i++){
        while(Direction(stack[top-1],stack[top],Q[i])>=0){
            top--;
        }
        stack[++top]=Q[i];
    }
    //最后stack里面就是逆时针的凸包点
}

旋转卡壳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long area(Point p0, Point p1, Point p2) {//这里算的是三角形面积的两倍
    return llabs((p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x));
}
long long dis(Point p1, Point p2) {//这里算的是两个点距离的平方
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
long long rotatingCalipers() {//返回凸包上最远的点对距离的平方
    int j = 2;
    stack[++top] = stack[0];//要在凸包集合末尾加上最初的点，保证枚举所有边
    if (top < 3) { return dis(stack[0], stack[1]); }
    long long max = 0;
    for (int i = 0; i < top; i++) {
        while (area(stack[i], stack[i + 1], stack[j]) <= area(stack[i], stack[i + 1], stack[j % top + 1]))j = j % top + 1;
        long long tmp = max(dis(stack[i], stack[j]), dis(stack[i + 1], stack[j]));
        max = max(max, tmp);
    }
    return max;
}

二维点对的查找

对所有点进行重复坐标的合并，并增加其点的个数

按照x升序，y再升序进行排列，查找某个点xy时，先查找x的左侧和右侧边界，然后在确定的边界内查找y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int binarySearchLeft(int x, int left, int right) {
    int saveRight = right;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (s[mid].x < x)left = mid + 1;
        else right = mid - 1;
    }
    if (left > saveRight || s[left].x != x)return -1;
    else return left;
}

int binarySearchRight(int x, int left, int right) {
    int saveLeft = left;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (s[mid].x > x)right = mid - 1;
        else left = mid + 1;
    }
    if (right < saveLeft || s[right].x != x)return -1;
    else return right;
}

int binarySearch(int x, int y, int left, int right) {
    int L = binarySearchLeft(x, left, right);
    int R = binarySearchRight(x, left, right);
    if (L == -1 || R == -1)return 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (s[mid].y < y)L = mid + 1;
        else if (s[mid].y > y)R = mid - 1;
        else return s[mid].cnt;
    }
    return 0;
}

三角形三条边长度确定外接圆坐标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long GP(long long x) {
    return x * x;
}
//获取圆心坐标
long double site[2];
void getCirclePoint(Point A, Point B, Point C) {
    long double x = (long double) ((GP(A.x) + GP(A.y)) * (B.y - C.y) + (GP(B.x) + GP(B.y)) * (C.y - A.y) + (GP(C.x) + GP(C.y)) * (A.y - B.y)) / (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2;
    long double y = (long double) ((GP(A.x) + GP(A.y)) * (C.x - B.x) + (GP(B.x) + GP(B.y)) * (A.x - C.x) + (GP(C.x) + GP(C.y)) * (B.x - A.x)) / (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) / 2;
    site[0] = x;
    site[1] = y;
}
long double calDisCircleToLine(Point cir[], Point line[]) {
    getCirclePoint(cir[0], cir[1], cir[2]);
    long double r = sqrtl((site[0] - cir[0].x) * (site[0] - cir[0].x) + (site[1] - cir[0].y) * (site[1] - cir[0].y));
    long double dis = fabsl((site[0] - line[0].x) * (site[1] - line[1].y) - (site[1] - line[0].y) * (site[0] - line[1].x)) / distance(line[0], line[1]);
    if (dis > r)return dis - r;
    else return 0.00;
}