计算几何笔记 （模板）
Froggy
2019-12-08 21:07:40
正弦定理:
$d_{circumcircle}= \frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}$
---
余弦定理:
$a^2=b^2+c^2-2bc \times \cos A$
$b^2=a^2+c^2-2ac \times \cos B$
$c^2=a^2+b^2-2ab \times \cos C$
---
向量旋转:
$\begin{bmatrix}\cos \theta &-\sin \theta\\\sin \theta&\cos \theta\end{bmatrix} \times \begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}x^\prime\\y^\prime\end{bmatrix}$
---
### 向量基本操作:
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define N 100010
using namespace std;
const double eps=1e-10;
const double PI=acos(-1.0);
//Vector可以用Point来表示
struct Point{
double x,y;
Point(){} Point(double _x,double _y){x=_x,y=_y;}
//相等
inline bool operator ==(Point b){
return fabs(x-b.x)<=eps&&fabs(y-b.y)<=eps;
}
//不相等
inline bool operator !=(Point b){
return !((*this)==b);
}
//相加
inline Point operator +(Point b){
return Point(x+b.x,y+b.y);
}
//相减
inline Point operator -(Point b){
return Point(x-b.x,y-b.y);
}
//点积
inline double operator *(Point b){
return x*b.x+y*b.y;
}
//叉积
inline double operator %(Point b){
return x*b.y-y*b.x;
}
//长度
inline double len(){
return sqrt(x*x+y*y);
}
//单位向量
inline Point unit(){
double tmp=len();
return Point(x/tmp,y/tmp);
}
//求单位法向量
inline Point normal(){
double tmp=len();
return Point(-y/tmp,x/tmp);
}
//点从下往上排序
inline bool operator <(Point b){
return fabs(y-b.y)<eps?x<b.x:y<b.y;
}
//平面直角坐标系上半部分优先
inline bool Quad(){
return y>eps||(fabs(y)<=eps&&x>=-eps);
}
}LTL;//Lower Then Left
inline Point operator *(double k,Point a){
return Point(a.x*k,a.y*k);
}
```
```cpp
//两个向量的夹角
inline double Angle(Point a,Point b){
//return acos(a*b/a.len()/b.len());
double tmp=atan2(b.y,b.x)-atan2(a.y,a.x);
while(tmp>=PI+eps)tmp-=2*PI;
while(tmp<=-PI-eps)tmp+=2*PI;
return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
return fabs(a%b)<=eps;
}
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
return b%a>eps;
}
//逆时针旋转p后的向量
inline Point Rotate(Point a,double p){
return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序
inline bool cmp(Point a,Point b){
a=a-LTL,b=b-LTL;
return Para(a,b)?a.len()<b.len():Left(b,a);
}
```
### 直线:
```cpp
//直线
struct Line{
Point p[2];
Line(){} Line(Point a,Point b){p[0]=a,p[1]=b;}
inline Point& operator [] (int i){
return p[i];
}
inline Point v(){
return p[1]-p[0];
}
};
//直线交点
inline Point Cross(Line a,Line b){
return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
}
```
### 多边形:
```cpp
//多边形
typedef vector<Point> Poly;
//面积
inline double Area(Poly a){
double tot=0;
for(int i=0;i<a.size()-1;i++){
tot+=a[i]%a[i+1];
}
tot+=a[a.size()-1]%a[0];
return fabs(tot)/2.0;
}
//周长
inline double C(Poly a){
double tot=0;
for(int i=0;i<a.size()-1;i++){
tot+=(a[i+1]-a[i]).len();
}
tot+=(a[a.size()-1]-a[0]).len();
return tot;
}
//重心
inline Point Cent(Poly a){
double x=0,y=0,m=0;
for(int i=1;i<a.size()-1;++i){
double tmp=(a[i]-a[0])%(a[i+1]-a[0]);
x+=tmp*(a[0].x+a[i].x+a[i+1].x)/3.0;
y+=tmp*(a[0].y+a[i].y+a[i+1].y)/3.0;
m+=tmp;
}
return Point(x/m,y/m);
}
```
### 凸包:
```cpp
//求凸包 (的周长)
Point st[123456];
int top;
inline double Convex(Poly a){
top=0;
LTL=(*min_element(a.begin(),a.end()));
sort(a.begin(),a.end(),cmp);
for(int i=0;i<a.size();++i){
while(top>1&&!Left(a[i]-st[top-1],st[top]-st[top-1]))--top;
st[++top]=a[i];
}
Poly tmp;
for(int i=1;i<=top;i++)tmp.push_back(st[i]);
return C(tmp);
}
```
### 点与多边形关系:
```cpp
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly a,Point p){
double tot=0;
for(int i=0;i<a.size();++i)tot+=Angle(a[i]-p,a[(i+1)%n]-p);
return fabs(tot)>=eps;
}
//多组询问
inline bool Inside_2(Poly &a,Point p){
if(p==LTL)return true;
if(Left(p-LTL,a[a.size()-1]-LTL)||Left(a[1]-LTL,p-LTL))return false;
int pos=lower_bound(a.begin(),a.end()-1,p,cmp)-a.begin();
return !Left(a[pos]-a[pos-1],p-a[pos-1])&<L<p;
}
```
### 半平面交:
```cpp
//半平面交(HalfPlaneIntersection)
inline bool cmpang(Point a,Point b){
return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Line q[N];
int l,r;
Poly HPI(Line L[],int m){
sort(L+1,L+m+1);
Poly R;
r=1,q[l=1]=L[1];
for(int i=2;i<=m;i++){
if(!cmpang(q[r].v(),L[i].v()))continue;
while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
q[++r]=L[i];
}
while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
q[r+1]=q[l];
for(int i=l;i<=r;++i){
R.push_back(Cross(q[i],q[i+1]));
}
return R;
}
```
### Minkowski和:
```cpp
//Minkowski
Poly Minkowski(Poly a,Poly b){
Poly R;
int i=0,j=0;
R.push_back(a[0]+b[0]);
while(1){
if(Left(a[(i+1)%a.size()]-a[i],b[(j+1)%b.size()]-b[j])){
j=(j+1)%b.size();
}
else{
i=(i+1)%a.size();
}
Point tmp=a[i]+b[j];
if(R.size()>1&&Para(tmp-R[R.size()-1],R[R.size()-1]-R[R.size()-2])){
R.pop_back();
}
R.push_back(tmp);
if(!i&&!j)break;
}
R.pop_back();
return R;
}
```
### 旋转卡壳:
```cpp
int RC(Poly a){
int ans=0,j=1;
a.push_back(a[0]);
for(int i=0;i<a.size()-1;++i){
while((a[i]-a[j])%(a[i+1]-a[j])<(a[i]-a[j+1])%(a[i+1]-a[j+1]))j=(j+1)%a.size();
ans=max(ans,max((a[j]-a[i]).len(),(a[j]-a[i+1]).len()));
}
return ans;
}
```