求pi

double pi=acos(-1.0);

求叉积

int cross = (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1);
        
if (cross < 0) allPositive = false;
if (cross > 0) allNegative = false;
    
return allPositive || allNegative;

求极角

atan2(double y, double x)

循环极角判断

求每个点之间的最大极角

    for(int i=1;i<cnt1;i++)
    {
      ans1=max(ans1,q1[i+1]-q1[i] );
    }
    ans1 = max(ans1, 2*pi - (q1[cnt1] - q1[1]));

矩形三点，求第四点：

void get_4th(int x1, int y1, int x2, int y2, int x3, int y3, int i) {
    //已知A(x1,y1),B(x2,y2),C(x3,y3)，求D(x4,y4)
    //ab表示AB^2,ac表示AC^2,BC表示BC^2
    int ab=pingfang(x1-x2)+pingfang(y1-y2),
        ac=pingfang(x1-x3)+pingfang(y1-y3),
        bc=pingfang(x2-x3)+pingfang(y2-y3);
    int x4,y4;
    //用勾股定理的逆定理，判断谁是直角边
    //再根据矩形对边平行的性质，算出第四个点的坐标
    if (ab+ac==bc) x4=x2+x3-x1, y4=y2+y3-y1;
    if (ab+bc==ac) x4=x1+x3-x2, y4=y1+y3-y2;
    if (ac+bc==ab) x4=x1+x2-x3, y4=y1+y2-y3;
    a[i+3].x=x4;
    a[i+3].y=y4;
}

将(x,y)绕原点(0,0)旋转 α 后的点的坐标为(x cosα − y sinα , y cosα + x sinα )

多边形形面积公式（叉积计算）

double calcs()
{
  double res=0;
  for(int i=2;i<cnt;i++)
  {
    res+=( a[i]-a[1] ).crs( a[i+1]-a[1] );
    //三角形的叉积面积计算
  }
  return res/2;
}

直线是否穿过矩形

// 计算在一个方向上圆心进入和退出矩形的时间区间
pair<double, double> compute_time(double p, double v, double l, double r) {
    if(v==0){
        if (p >= l && p <= r) {
            return {0.0, INF}; // 始终满足条件
        }
        else {
            return {INF, -INF}; // 无效的时间区间
        }
    }
    else{
        double tl=(l-p)/v,tr=(r-p)/v;
        if( v>0 )
        return { tl,tr };
        return { tr,tl };
    }
}

        // 计算x方向和y方向的时间区间
        pair<double, double> tx = compute_time(x, vx, min_x, max_x);
        pair<double, double> ty = compute_time(y, vy, min_y, max_y);

        // 取时间区间的交集
        double t_min = max(tx.first, ty.first);
        double t_max = min(tx.second, ty.second);

        // 时间不能为负数
        t_min = max(t_min, 0.0);

        // 判断是否存在满足条件的时间
        if(t_min <= t_max ){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }

凹多边形的性质

在算法竞赛的计算几何问题中，凹多边形的性质常被用于判断多边形类型、处理包含关系、优化几何计算等场景。以下是其核心性质及应用场景总结：

1. 内角与外角的核心特征

• 定义性性质：凹多边形至少存在一个内角大于180°（对应的外角为负角度），这是区分凹/凸多边形的核心标志。
• 算法应用：通过连续三个顶点的转向（叉积判断）可检测这一特征：
  对多边形顶点序列 ( P_0, P_1, ..., P_{n-1} )，计算相邻三点 ( P_i, P_{i+1}, P_{i+2} ) 的叉积 ( \overrightarrow{P_iP_{i+1}} \times \overrightarrow{P_{i+1}P_{i+2}} )。若所有叉积符号一致（均正或均负，凸多边形），若存在符号相反的叉积（包括零，需排除共线），则为凹多边形。

2. 对角线的“外部性”

• 性质：凸多边形的所有对角线（非相邻顶点连线）均在多边形内部；而凹多边形至少存在一条对角线在外部（例如从凹陷顶点到对边的连线可能穿出多边形）。
• 算法应用：在多边形三角剖分（将多边形分割为三角形）中，凹多边形的剖分需避免选择外部对角线，需额外判断对角线是否完全在多边形内（可通过点与线段的位置关系验证）。

3. 凸包与自身的关系

• 性质：凹多边形的凸包（最小凸多边形）一定包含自身，且凸包面积大于凹多边形面积；凸多边形的凸包就是自身，面积相等。
• 算法应用：
  • 可通过对比多边形面积与凸包面积判断凹凸性（面积不等则为凹）；
  • 在“点是否在多边形内”的预处理中，若点在凸包外，则一定在多边形外（快速排除）。

4. 点在多边形内的判断兼容性

• 性质：凹多边形的“点在内部”判断逻辑与凸多边形一致（通用射线法/转角法），但需注意凹陷区域可能导致射线多次穿过边界（需严格按“穿过次数奇偶性”判断：奇数次在内部，偶数次在外部）。
• 算法应用：无需因多边形凹凸调整核心判断逻辑，但需确保边界处理（如点在边上的情况）一致。

5. “凹陷顶点”的特殊性

• 性质：凹多边形中内角>180°的顶点称为“凹陷顶点”，该顶点的“凸出方向”与其他顶点相反（例如多边形整体逆时针时，凹陷顶点处为顺时针转向）。
• 算法应用：
  • 三角剖分时，凹陷顶点不能作为“耳点”（耳点指相邻两边形成的角内无其他顶点），需优先处理非凹陷顶点；
  • 在碰撞检测中，凹陷顶点是多边形“向内凹”的位置，可能导致特殊的重叠区域。

6. 面积计算的一致性

• 性质：凹多边形的面积计算仍可使用“叉积求和法”（与凸多边形相同）：
  面积 = ( \frac{1}{2} |\sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i)| )（( P_n = P_0 )），结果为多边形“实际包围区域”的面积（凹陷部分会抵消多余面积）。
• 算法应用：无需区分凹凸，直接套用公式计算面积，结果自动修正凹陷部分的影响。

总结：算法竞赛中的关键应用

凹多边形的核心考点集中在凹凸性判断（叉积符号）、几何操作适配（如三角剖分、凸包），以及利用其与凸多边形的差异优化逻辑（如快速排除凸包外的点）。掌握“转向判断”和“凸包关系”是处理凹多边形问题的基础。

在算法竞赛中，凸多边形的性质是几何类问题的核心基础（许多场景会先通过凸包将问题转化为凸多边形处理）。其性质的核心特点是“结构规则性”，这使得相关计算和判断更高效。以下是常用性质及结论：

一、核心判定性质（区分凸/凹的关键）

1. 转向一致性
   • 性质：对凸多边形的顶点序列（按顺时针/逆时针排列），任意连续三个顶点 ( P_i, P_{i+1}, P_{i+2} ) 的转向（叉积符号）完全一致：
     若整体为逆时针（常用），则所有叉积 ( \overrightarrow{P_iP_{i+1}} \times \overrightarrow{P_{i+1}P_{i+2}} \geq 0 )（非负，共线顶点允许为0）；
     若整体为顺时针，则所有叉积 ( \leq 0 )。
     （凹多边形存在叉积符号相反的情况）
   • 应用：这是判断多边形是否为凸多边形的唯一标准，算法中直接通过遍历所有连续三点的叉积符号实现。

二、几何结构的“内部封闭性”

2. 对角线全在内部

   • 性质：凸多边形中，任意两个非相邻顶点的连线（对角线）一定完全在多边形内部；且任意一条边的延长线不会穿过多边形内部。
   • 应用：
     • 三角剖分无需额外判断对角线合法性（任意连接非相邻顶点即可，如从一个顶点出发连接所有非相邻顶点，直接分成 ( n-2 ) 个三角形）；
     • 处理“多边形内两点连线是否穿过边界”时，凸多边形中只需判断连线是否为对角线（是则在内部，无需复杂检测）。

3. 凸包与自身完全重合

   • 性质：凸多边形的凸包（最小包含它的凸多边形）就是自身，因此：
     • 凸包的顶点集与原多边形顶点集一致（仅可能按顺序调整）；
     • 凸包面积 = 原多边形面积。
   • 应用：
     • 判断多边形凹凸性：若多边形与自身凸包面积相等（或顶点集完全重合），则为凸多边形；
     • 简化计算：无需对凸多边形做“凸包预处理”，直接用原顶点操作。

三、高效的“点与多边形”关系判断

4. 点在内部的快速判定（优于凹多边形）

   • 性质：对凸多边形，判断点 ( Q ) 是否在内部，无需用通用的“射线法”（复杂度 ( O(n) )），可通过叉积符号一致性实现：
     若多边形顶点按逆时针排列，只需判断 ( Q ) 与所有边 ( P_iP_{i+1} ) 的叉积 ( \overrightarrow{P_iP_{i+1}} \times \overrightarrow{P_iQ} \geq 0 )（即点在所有边的“左侧”），则在内部（包括边界）。
   • 优化：结合二分法可将复杂度降至 ( O(\log n) )（利用凸多边形顶点的单调性，见下文）。

5. 边界点的明确性

   • 性质：凸多边形的边界（边）上的点，一定满足“在某条边的线段上”，且不会因“凹陷”产生复杂的边界嵌套（凹多边形可能有边在内部区域交叉的视觉错觉，但实际边界不交叉）。
   • 应用：判断“点是否在边界上”时，直接检查点是否在任意一条边上（无需考虑凹陷导致的特殊情况）。

四、顶点的“单调性与极值性”

6. 顶点的坐标单调性

   • 性质：凸多边形的顶点按逆时针（或顺时针）排列时，其 ( x ) 坐标和 ( y ) 坐标具有“局部单调性”，且极值点（如x最大、x最小、y最大、y最小）一定是顶点（不会出现在边上）。
   • 应用：
     • 快速定位极值点（如找x最大的顶点，直接遍历顶点比较即可，无需检查边）；
     • 基于单调性的二分查找：例如按x排序的凸多边形顶点，可二分定位点可能所在的边区间（用于优化“点在内部”的判断）。

7. 相邻顶点的“有序性”

   • 性质：凸多边形的顶点按逆时针排列时，其极角（相对于某个内部点）是严格递增的；按x坐标排序时，相邻顶点的连线斜率单调变化。
   • 应用：在旋转卡壳（Rotating Calipers）算法中，利用顶点有序性高效求解凸多边形的直径（最远顶点对）、最小外接矩形等问题（复杂度 ( O(n) )）。

五、面积与距离相关的特殊结论

8. 面积计算的直接性

   • 性质：与凹多边形相同，凸多边形面积可通过“叉积求和法”计算（( \frac{1}{2} |\sum (x_i y_{i+1} - x_{i+1} y_i)| )），但由于无凹陷，面积就是“所有三角形面积之和”（无需抵消凹陷部分）。
   • 应用：计算结果可直接用于与凸包面积对比（判断凹凸性），或作为其他计算的基础（如重心坐标）。

9. 最远/最近点对的存在性

   • 性质：凸多边形的最远顶点对（直径）一定是凸包上的顶点对（而凸多边形的凸包是自身，因此最远点对是其某两个顶点）；最近点对可能是相邻顶点（但不一定，需遍历检测）。
   • 应用：旋转卡壳算法的核心依据——通过同步旋转两条平行线，遍历顶点即可找到最远点对（无需 ( O(n^2) ) 枚举）。

六、与其他凸图形的兼容性

10. 凸集的封闭性
    • 性质：凸多边形是“凸集”——任意两点的连线完全在多边形内。这意味着：
      • 两个凸多边形的交集仍是凸集（可能为空、点、线段或凸多边形）；
      • 凸多边形的缩放、平移后仍为凸多边形。
    • 应用：在“凸多边形交”问题中，可通过边的有序性高效求解（如用双指针遍历两个凸多边形的边）。

总结：算法竞赛中的核心应用场景

凸多边形的价值在于**“规则性带来的高效计算”**：

• 判定：用叉积符号一致性（( O(n) )）；
• 点在内部：用叉积+二分（( O(\log n) )）；
• 优化转化：通过凸包将凹多边形/点集转化为凸多边形，再用旋转卡壳、二分等高效算法；
• 几何操作：三角剖分、交并计算等因结构规则大幅简化。

掌握这些性质是解决“凸包相关问题”“最远点对”“多边形交”等经典题目的基础。