凹凸多边形的判断

重要知识：叉积

几何意义：

符号代表了叉积两个向量的转向：
> 0 逆时针
< 0 顺时针
= 0 共线

基本原理

对于连续三个点A、B、C：
叉积 = (B.x - A.x) (C.y - B.y) - (B.y - A.y) (C.x - B.x)
要是是向量的话是：a.x b.y- a.y b.x

这个叉积实际上计算的是向量 AB 到向量 BC 的旋转方向。

实现方法

可视化解释

考虑四边形$ABCD$，我们按顺序（如逆时针）检查每个顶点：

如果所有顶点的叉积都保持同号（全部为正或全部为负），说明多边形所有顶点都朝同一个方向”拐弯”，这就是凸多边形。

1
2
3
4
C(2,2) ────── D(0,2)
│              │
│              │
B(2,0) ────── A(0,0)

在顶点A处：

  • 向量DA = A - D = (0-0, 0-2) = (0, -2)
  • 向量AB = B - A = (2-0, 0-0) = (2, 0)
  • DA × AB = 0 0 - (-2) 2 = 4 > 0（逆时针）

在顶点B处：

  • 向量AB = (2, 0)
  • 向量BC = C - B = (2-2, 2-0) = (0, 2)
  • AB × BC = 2 2 - 0 0 = 4 > 0（逆时针）

凹四边形的反例

对于凹四边形，某个顶点会出现相反的转向：

1
2
3
     D(1,2)
    /B(1,1) ← 凹点
A(0,0)─-───────C(3,0)

在凹点B处，转向会与其他顶点相反。

算法实现步骤

  • 计算各个叉积
1
2
3
4
cp₁ = 叉积(向量AB, 向量BC)  // 在点B处
cp₂ = 叉积(向量BC, 向量CD)  // 在点C处
cp₃ = 叉积(向量CD, 向量DA)  // 在点D处
cp₄ = 叉积(向量DA, 向量AB)  // 在点A处
    1. 判断符号一致性：
      • 如果所有$cp_i \geq 0$，则为逆时针排列的凸四边形
      • 如果所有$cp_i\leq 0$，则为顺时针排列的凸四边形
      • 否则为凹四边形

实例代码

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
struct point{double x,y;};

double chaji(const point &a,const point &b,const point &c{
  point v1,v2;//计算向量
  v1.x=b.x-a.x; v1.y=b.y-a.y;
  v2.x=c.x-b.x; v2.y=c.y-b.y;
  return v1.x*v2.y-v1.y*v2.x;
  //转换成向量以后，x和y交换着乘
}

void solve(){
  point a,b,c,d;
  cin>>a.x>>a.y;
  cin>>b.x>>b.y;
  cin>>c.x>>c.y;
  cin>>d.x>>d.y;
  double cj1=chaji(a,b,c);
  double cj2=chaji(b,c,d);
  double cj3=chaji(c,d,a);
  double cj4=chaji(d,a,b);
  if((cj1>0&&cj2>0&&cj3>0&&cj4>0)||(cj1<0&&cj2<0&&cj3<0&&cj4<0)){
    cout<<"Yes"<<endl;//要同号才行
  }
  else cout<<"No"<<endl;
}
signed main(){
    solve();
    return 0;
}

直线的计算

写在前面的话

傻逼C++的double的精度不高所以表示直线建议使用$Ax+By+C=0$

然后就变简单了喵~

计算公式

之后不要忘记除以他们的最大公约数，用来去重，这点非常重要，因为可能产生倍数

例题

K-colinear Line

这一题要求我们计算经过k个点的直线数量，这里最重要的是理解怎么消去除法。
这题的做法还是蛮多样的，好友qinye_leaf的解法是：
此外上面的做法也是可行的，总之消去除法，然后防止重复(这是一个好问题)

圆的计算

$\pi$的取值建议

  • 如果有了规定值，那么直接使用
  • 没有的话，处于精度考虑，可以使用$\arccos (1.0)$来代替、

    多边形的计算

几何图形面积计算

例一

例题：P. Area of a Star
需要我们计算多角形的面积
这一题的话有两种做法，一种是直接分成$2*n$个小三角形，而每一个三角形的三个内角都是已知的，因此可以直接计算。
另外一种做法是发现可以整体减空白，稍微复杂一点，但也可行。

补充知识

复习一下正弦定理：
因此这一题只知道三个角和一条边是可以直接计算的。

例二

例题：B. Mister B and Angle in Polygon

需要我们在多边形上找到三个点，使得构成的角度和给定角度最接近。

重要观察：在正n边形中，从一个顶点出发，连接所有其他不相邻的顶点（即除相邻两个顶点外的所有顶点），这些连线会将这个顶点的内角等分成$n−2$个相等的角，每个角的度数为 $\frac{180}{n}$。

证明：把多边形放到一个圆里面，然后发现相同弦所对的角相等，所以原命题是成立的

推论：那么在这个多边形上任取三个点构成的角也必然是$\frac{180}{n}$.

证明：和刚才一样，只要证明每个条角所对的弦都能在同一个顶点上构造出来

所以解出这题的步骤是：

  • 先看是否大于等于最大角，如果是，那么输出1 2 3
  • 否则计算中间值用$\frac{180}{n}$的倍数代替。