2021.11.22 凸包
2021.11.22 凸包
虽然我菜吧，但也要菜得有水平！
1. 定义
1.1
简称用最短的线框住所有点。
1.2 叉乘cross
设点 \(O(0,0)\) , \(A(x1,y1)\) , \(B(x2,y2)\), \(OA=l1=\sqrt{x_1^2+y_1^2}\) , \(OB=l2=\sqrt{x_1^2+y_2^2}\) , \(\theta = <\overrightarrow{OA},\overrightarrow{OB}>\) , \(\alpha= <\overrightarrow{OX},\overrightarrow{OB}>\) , \(\beta= <\overrightarrow{OX},\overrightarrow{OA}>\)。
\[\sin(\theta)=\sin(\alpha-\beta)\\ =\sin\alpha\cos\beta-\cos\alpha\sin\beta\\ =\frac{y_2}{l_2}*\frac{x_1}{l_1}-\frac{x_2}{l_2}*\frac{y_1}{l_1}\\ \frac{y_2*x_1-x_2*y_1}{l_1*l_2}\\ \overrightarrow{OA}\times\overrightarrow{OB}=|OA|*|OB|*\sin\theta\\ =l_1*l_2*\frac{x_1*y_2-x_2*y_1}{l_1*l_2}\\ =x_1*y_2-x_2*y_1 \]1.3点乘dot
设点 \(O(0,0)\) , \(A(x1,y1)\) , \(B(x2,y2)\), \(OA=l1=\sqrt{x_1^2+y_1^2}\) , \(OB=l2=\sqrt{x_1^2+y_2^2}\) , \(\theta = <\overrightarrow{OA},\overrightarrow{OB}>\) , \(\alpha= <\overrightarrow{OX},\overrightarrow{OB}>\) , \(\beta= <\overrightarrow{OX},\overrightarrow{OA}>\)。
\[\cos(\theta)=\cos(\alpha-\beta)\\ =\cos\alpha\cos\beta+\sin\alpha\sin\beta\\ =\frac{x_2}{l_2}*\frac{x_1}{l_1}+\frac{y_2}{l_2}*\frac{y_1}{l_1}\\ \frac{x_2*x_1+y_2*y_1}{l_1*l_2}\\ \overrightarrow{OA}\cdot\overrightarrow{OB}=|OA|*|OB|*\sin\theta\\ =l_1*l_2*\frac{x_1*x_2+y_2*y_1}{l_1*l_2}\\ =x_1*x_2+y_2*y_1 \]1.4
两点相减：从被减的点到减它的点有一条向量
2. Andrew算法
如果只是从起点逆时针左转，可以得到一个下凸壳，然后从终点开始顺时针右转，可以得到一个上凸壳，吧唧，成了一个凸壳~
https://www.luogu.com.cn/problem/P2742
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int n,top,vis[N],stacki[N],fin[N];
struct node{
double x,y;
bool operator <(const node &b)const{
return x==b.x?y=2&&chacheng(stacki[top-1],stacki[top],stacki[top],i)<0)--top;
vis[i]=1;
stacki[++top]=i;
}
//for(int i=1;i<=top;i++)cout<=1;i--)
/*if(!vis[i])*/{
while(top>tmp&&chacheng(stacki[top-1],stacki[top],stacki[top],i)<0)
vis[stacki[top]]=0,--top;
vis[i]=1;
stacki[++top]=i;
}
//for(int i=1;i<=top;i++)cout<>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
tubao();
return 0;
}
https://www.luogu.com.cn/problem/UVA11626
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int N=1e5+10;
int t,n,top,stacki[N];
struct node{
int x,y;
bool operator <(const node &b)const{
return x==b.x?y=2&&chacheng(stacki[top-1],stacki[top],i)<0)--top;
stacki[++top]=i;
}
int tmp=top;
stacki[++top]=n-1;
for(int i=n-2;i>=1;i--){
while(top>tmp&&chacheng(stacki[top-1],stacki[top],i)<0)--top;
stacki[++top]=i;
}
//for(int i=1;i<=top;i++)cout<>t;
while(t--){
cin>>n;
top=0;
memset(stacki,0,sizeof(stacki));
//memset(&a,0,sizeof(a));
int ni=n;n=0;
for(int i=1;i<=ni;i++){
int x,y;
char ch;
cin>>x>>y>>ch;
//if(ch=='N')continue;
++n;
a[n].x=x;a[n].y=y;
}
tubao();
}
return 0;
}
https://www.luogu.com.cn/problem/P2521
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int n,m,X,Y,top,vis[N];
double ans,river;
struct node{
double x,y;
int id;
bool operator <(const node &b)const{
return x==b.x?y=2&&cross(stacki[top]-stacki[top-1],a[i]-stacki[top])<=0)
vis[stacki[top].id]=0,--top;
stacki[++top]=a[i];
vis[stacki[top].id]=1;
}
}
int tmp=top;
for(int i=n-1;i>=1;i--)if(vis[a[i].id]!=2){
while(top>tmp&&cross(stacki[top]-stacki[top-1],a[i]-stacki[top])<=0)
vis[stacki[top].id]=0,--top;
stacki[++top]=a[i];
vis[stacki[top].id]=1;
}
//cout<<"array stacki[i]"<>n;river=n;
a[1].x=a[1].y=0;a[1].id=1;
a[2].x=n;a[2].y=0;a[2].id=2;
cin>>X>>Y;
a[3].x=X;a[3].y=Y;a[3].id=3;
cin>>n;
for(int i=4;i<=n+3;i++)cin>>a[i].x>>a[i].y,a[i].id=i;
n+=3;
sort(a+1,a+n+1);
cin>>m;
Andrew();
int flag=0;
for(int i=1;i<=m;i++){
int op,x;
cin>>op;
if(op==2){
if(flag==1)Andrew(),flag=0;
printf("%.2lf\n",ans-river);
}else if(op==1){
cin>>x;x+=3;
if(vis[x]==1)flag=1;
vis[x]=2;
}
}
return 0;
}
https://www.luogu.com.cn/problem/P3829
PS：本题应用转角公式，以及pi为 acos(-1.0) 。
//这道题和UVA1303不能说很像，只能说一模一样
#include
#include
#include
#include
#include
using namespace std;
const int N=4e4+10;
int n,top;
double A,B,R;
struct node{
double x,y;
bool operator <(const node &b)const{
return x==b.x?y=2&&cross(stacki[top]-stacki[top-1],a[i]-stacki[top])<=0)--top;
stacki[++top]=a[i];
}
int tmp=top;
stacki[++top]=a[n-1];
for(int i=n-2;i>=1;i--){
while(top>tmp&&cross(stacki[top]-stacki[top-1],a[i]-stacki[top])<=0)--top;
stacki[++top]=a[i];
}
double ans=(double)R*acos(-1.0)*2;
for(int i=1;i>n;
cin>>B>>A>>R;
A/=2.0;B/=2.0;
for(int i=1;i<=n;i++){
double x,y,theta;
cin>>x>>y>>theta;
node jz=(node){x,y};
a[(i-1)*4+1]=rotate((node){A-R,B-R},theta)+jz;
a[(i-1)*4+2]=rotate((node){-A+R,-B+R},theta)+jz;
a[(i-1)*4+3]=rotate((node){A-R,-B+R},theta)+jz;
a[(i-1)*4+4]=rotate((node){-A+R,B-R},theta)+jz;
}
Andrew();
return 0;
}
3. Graham算法
http://poj.org/problem?id=1113
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1010;
int n,l,stacki[N],top;
struct node{
double x,y;
}a[N];
inline int chacheng(node x,node y,node z){
return (y.x-x.x)*(z.y-y.y)-(y.y-x.y)*(z.x-y.x);
}
inline double dis(node x,node y){
return (double)sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline bool cmp(node x,node y){
int ans=chacheng(a[0],x,y);
if(ans>0)return true;
if(ans==0&&dis(a[0],x)a[i].y))aim=i;
swap(a[aim],a[0]);
sort(a+1,a+n,cmp);
top=-1;
stacki[++top]=0;stacki[++top]=1;stacki[++top]=2;
for(int i=3;i=2&&chacheng(a[stacki[top-1]],a[stacki[top]],a[i])<0)--top;
stacki[++top]=i;
}
stacki[++top]=stacki[0];
//for(int i=0;i<=top;i++)cout<>a[i].x>>a[i].y;
Graham();
}
return 0;
}
4.旋转卡壳
此标题共有 \(2^4\) 种读法，我选择……你猜？
https://blog.csdn.net/qq_30974369/article/details/76408050
模板：
https://www.luogu.com.cn/problem/P1452
#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int N=5e4+10;
int n,stacki[N],top,vis[N];
struct node{
int x,y;
bool operator <(const node &b)const{
return x==b.x?y=2&&chacheng(stacki[top-1],stacki[top],i)<=0)--top;
stacki[++top]=i;
}
int tmp=top;
stacki[++top]=n-1;
for(int i=n-2;i>=1;i--){
while(top>tmp&&chacheng(stacki[top-1],stacki[top],i)<=0)--top;
stacki[++top]=i;
}
}
inline int maxn(){
int ans=0;
int aim=2;
for(int i=1;i>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
Andrew();
cout<
4.1 最小矩形覆盖
https://www.luogu.com.cn/problem/P3187
只需要输出一个换行就行，呵呵了，破样例！！
// https://www.luogu.com.cn/blog/Huah/solution-p3187
#include
#include
#include
#include
#include
using namespace std;
const int N=5e4+10;
int n,stacki[N],top;
struct node{
double x,y;
bool operator <(const node &b)const{
return x==b.x?y=2&&cross(a[stacki[top]]-a[stacki[top-1]],a[i]-a[stacki[top]])<=0)--top;
stacki[++top]=i;
}
int tmp=top;
stacki[++top]=n-1;
for(int i=n-2;i>=1;i--){
while(top>tmp&&cross(a[stacki[top]]-a[stacki[top-1]],a[i]-a[stacki[top]])<=0)--top;
stacki[++top]=i;
}
/*cout<<"stacki"<=
dot(a[stacki[r%top+1]]-a[stacki[i]],a[stacki[i-1]]-a[stacki[i]]))r=r%top+1;
if(i==2)l=h;
while(dot(a[stacki[l]]-a[stacki[i-1]],a[stacki[i]]-a[stacki[i-1]])>=
dot(a[stacki[l%top+1]]-a[stacki[i-1]],a[stacki[i]]-a[stacki[i-1]]))l=l%top+1;
double len=dis(a[stacki[i]],a[stacki[i-1]]);
double L=dot(a[stacki[l]]-a[stacki[i]],a[stacki[i-1]]-a[stacki[i]])/len;
double R=dot(a[stacki[r]]-a[stacki[i-1]],a[stacki[i]]-a[stacki[i-1]])/len;
double H=cross(a[stacki[i]]-a[stacki[h]],a[stacki[i-1]]-a[stacki[h]])/len;
L=fabs(L);R=fabs(R);H=fabs(H);
double now=(L+R-len)*H;
//cout<>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
Andrew();find();
int start=0;fin[0].y=1e9,fin[0].x=1e9;
for(int i=1;i<=4;i++)if(fin[i].y
4.2最小圆覆盖
实际上和旋转卡壳并没有什么关系，但是因为信号塔这一题旋转卡壳+凸包+模拟退火写崩了让我很不爽，所以放在这里。
已知圆的标准方程为 \((x-x_0)^2+(y-y_0)^2=r^2\) ，设 \(P_1=(x_1,y_1)\) ，\(P_2=(x_2,y_2)\) ，\(P_3=(x_3,y_3)\) 。
\[\begin{equation}
\begin{cases}
(x_1-x_0)^2+(y_1-y_0)^2=r^2\\
(x_2-x_0)^2+(y_2-y_0)^2=r^2\\
(x_3-x_0)^2+(y_3-y_0)^2=r^2\\
\end{cases}
\end{equation}
\Longrightarrow
\begin{cases}
(x_1-x_2)*x_0+(y_1-y_2)*y_0=\frac{(x_1^2-x_2^2)-(y_2^2-y_1^2)}{2}\\
(x_1-x_3)*x_0+(y_1-y_3)*y_0=\frac{(x_1^2-x_3^2)-(y_3^2-y_1^2)}{2}\\
\end{cases}
\]设 \(a=x_1-x_2\) , \(b=y_1-y_2\) , \(c=x_1-x_3\) , \(d=y_1-y_3\) ,
\[e=\frac{(x_1^2-x_2^2)-(y_2^2-y_1^2)}{2}$$ ,
$$f=\frac{(x_1^2-x_3^2)-(y_3^2-y_1^2)}{2}$$ 。
\]\begin{equation}
原式=
\begin{cases}
ax_0+by_0=e\
cx_0+dy_0=f\
\end{cases}
\end{equation}
\[
\]解得：\
\begin{cases}
x_0=\frac{fb-ed}{cb-ad}\
y_0=\frac{ec-fa}{cd-ad}\
\end{cases}
\[
**random_shuffle**
https://blog.csdn.net/u010296599/article/details/58596814
https://www.luogu.com.cn/problem/P1742
```c++
#include
#include
#include
#include
#include
using namespace std;
const int N=5e5+10;
const double eps=1e-12;
int n;
double R;
struct node{
double x,y;
}a[N],O;
inline double dis(node x,node y){
return (double)sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline void find(node p1,node p2,node p3){
//实验1号：目的：验证式子是否正确
double a=p1.x-p2.x,b=p1.y-p2.y;
double c=p1.x-p3.x,d=p1.y-p3.y;
double e=(p1.x*p1.x-p2.x*p2.x)-(p2.y*p2.y-p1.y*p1.y);e/=2.0;
double f=(p1.x*p1.x-p3.x*p3.x)-(p3.y*p3.y-p1.y*p1.y);f/=2.0;
O.x=(f*b-e*d)/(c*b-a*d);
O.y=(e*c-f*a)/(c*b-a*d);
R=dis(O,p1);
}
inline void Circle(){
random_shuffle(a+1,a+n+1);
O=a[1];R=0.0;
for(int i=2;i<=n;i++)if(dis(O,a[i])>R+eps){
O=a[i];R=0.0;//枚举圆心
for(int j=1;jR+eps){
O.x=(a[i].x+a[j].x)/2;
O.y=(a[i].y+a[j].y)/2;
R=dis(O,a[j]);//已经确定两个点，两个点连成直线，圆心先放在两个点中点
for(int k=1;kR+eps)
find(a[i],a[j],a[k]);//找到第三个点（在j之前），这个点不在已知的圆内，求三点共圆
}
}
printf("%.10lf\n%.10lf %.10lf",R,O.x,O.y);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
Circle();
return 0;
}
```
https://www.luogu.com.cn/problem/P4288
注：把椭圆变成圆进行计算
```c++
#include
#include
#include
#include
#include
using namespace std;
const int N=5e4+10;
const double eps=1e-13;
int n;
double R;
struct node{
double x,y;
}a[N],O;
inline double cross(node x,node y){
return x.x*y.y-x.y*y.x;
}
inline double dot(node x,node y){
return x.x*y.x+x.y*y.y;
}
inline double dis(node x,node y){
return (double)sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline void findCross(node p1,node p2,node p3){
double a=p1.x-p2.x,b=p1.y-p2.y;
double c=p1.x-p3.x,d=p1.y-p3.y;
double e=(p1.x*p1.x-p2.x*p2.x)-(p2.y*p2.y-p1.y*p1.y);e/=2.0;
double f=(p1.x*p1.x-p3.x*p3.x)-(p3.y*p3.y-p1.y*p1.y);f/=2.0;
O.x=(f*b-e*d)/(b*c-a*d);
O.y=(e*c-f*a)/(b*c-a*d);
R=dis(O,p1);
}
inline void Circle(){
random_shuffle(a+1,a+n+1);
O=a[1];R=0.0;
for(int i=2;i<=n;i++)if(dis(O,a[i])>R+eps){
O=a[i];R=0.0;
for(int j=1;jR+eps){
O.x=(a[i].x+a[j].x)/2.0;
O.y=(a[i].y+a[j].y)/2.0;
R=dis(O,a[i]);
for(int k=1;kR+eps)findCross(a[i],a[j],a[k]);
}
}
printf("%.3lf",R);
}
inline node rotate(node x,double theta){
double sini=sin(theta),cosi=cos(theta);
return (node){x.x*cosi-x.y*sini,x.y*cosi+x.x*sini};
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
double theta,p;
cin>>theta>>p;
theta=(360.0-theta)/180.0*acos(-1.0);
p=1.0/p;
for(int i=1;i<=n;i++)a[i]=rotate(a[i],theta);
for(int i=1;i<=n;i++)a[i].x*=p;
Circle();
return 0;
}
```
### 5. 半平面交
当我好不容易打完的东西又没了，我的悲伤有亿点大！
#### 5.1 转角公式
设 $\overrightarrow{AB}$ 从 A 指向 B ，长度为 $l$ ，A与坐标原点重合，B的坐标为 $(x,y)$ ，角度为 $\alpha$ ，则 $l=\sqrt{x^2+y^2}$ 。将 $\overrightarrow{AB}$ 逆时针旋转 $\beta$ ，则
旋转前
\]\overrightarrow{AB}=(x,y)\
=(l\cos\alpha,l\sin\alpha)
\[旋转后
\]\overrightarrow{AB}=(l\cos(\alpha+\beta),l\sin(\alpha+\beta))\
=(l(\cos\alpha\cos\beta-\sin\alpha\sin\beta),l(\sin\alpha\cos\beta+\sin\beta\cos\alpha))\
=(x\cos\beta-y\sin\beta,y\cos\beta+x\sin\beta)
\[
#### 5.2 求向量与x轴夹角
设 $\overrightarrow{AB}$ 从 A 指向 B ，长度为 $l$ ，A与坐标原点重合，B的坐标为 $(x,y)$ ，角度为 $\alpha$ ，则
\]\alpha=atan2(y,x)
\[记得打头文件 **`#include`** !
#### 5.3 求两直线夹角
设 $\overrightarrow{a}$ 与 $\overrightarrow{b}$ 夹角为 $\theta$ ，两向量形成的平行四边形高为 $h$ ，高与两断点所连接的两边形成直角三角形，直角三角形两条直角边分别是高 $h$ 和在 $\overrightarrow{b}$ 上的底 $l$ 。
\]h=\overrightarrow{a}\times\overrightarrow{b}/|\overrightarrow{a}|\
l=\overrightarrow{a}\cdot\overrightarrow{b}/|\overrightarrow{a}|
\[则
\]\theta=atan2(h,l)\
=atan2(\overrightarrow{a}\times\overrightarrow{b}/|\overrightarrow{a}|,\overrightarrow{a}\cdot\overrightarrow{b}/|\overrightarrow{a}|)\
=atan2(\overrightarrow{a}\times\overrightarrow{b},\overrightarrow{a}\cdot\overrightarrow{b})
\[
#### 5.4 两直线交点
画完图放不上来，放上来还要打好多字，搞不好一不小心typora挂了，啥都没了 。
直接步入正题吧。
#### 5.5 半平面交
https://www.luogu.com.cn/problem/P4196
注：叉乘中两个向量的先后顺序不一样得出来的结果也不一样，毕竟 $\sin\theta$ 的值有正有负！
https://www.luogu.com.cn/blog/suxxsfe/solution-p4196
https://www.cnblogs.com/xzyxzy/p/10033130.html
```c++
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
const double eps=1e-13;//!
int L,R;
struct node{
double x,y;
inline node operator +(const node &b)const{
return (node){x+b.x,y+b.y};
}
inline node operator -(const node &b)const{
return (node){x-b.x,y-b.y};
}
}stain[N],Cross[N];
inline node operator *(node a,double k){
return (node){a.x*k,a.y*k};
}
inline node operator /(node a,double k){
return (node){a.x/k,a.y/k};
}
inline double cross(node x,node y){
return x.x*y.y-x.y*y.x;
}
inline double dot(node x,node y){
return x.x*y.x+x.y*y.y;
}
struct nodei{
node pos,vec;
double angle;
inline void add(node a,node b){//
pos=a;vec=b;
angle=atan2(b.y,b.x);
}
bool operator <(const nodei &b){
return angle>t;
while(t--){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>stain[i].x>>stain[i].y;
for(int i=1;i
#include
#include
#include
#include
using namespace std;
const int N=310;
const double eps=1e-13;
int n,L,R;
struct stain{
double x,y;
bool operator <(const stain &b)const{
return x==b.x?y>b.y:x>b.x;
}
stain operator +(const stain &b)const{
return (stain){x+b.x,y+b.y};
}
stain operator -(const stain &b)const{
return (stain){x-b.x,y-b.y};
}
stain operator *(const double &k)const{
return (stain){x*k,y*k};
}
stain operator /(const double &k)const{
return (stain){x/k,y/k};
}
}a[N],Cross[N];
inline double cross(stain x,stain y){
return x.x*y.y-x.y*y.x;
}
inline double dot(stain x,stain y){
return x.x*y.x+x.y*y.y;
}
struct line{
stain start,endi;
double angle;
bool operator <(const line &b)const{
if(fabs(angle-b.angle)>eps)return angleeps;
}
}p[N],stacki[N];
inline stain findCross(line x,line y){
stain vecx=x.endi-x.start;
stain vecy=y.endi-y.start;
stain vec=y.start-x.start;
double t=cross(vecy,vec)/cross(vecy,vecx);
return x.start+vecx*t;
}
inline void halfPlane(){
sort(p+1,p+n+1);
L=0,R=0;
for(int i=1;i<=n;i++)if(fabs(p[i].angle-p[i-1].angle)>eps||i==1){
/*while(R-L>1&&cross(p[i].endi-p[i].start,Cross[R]-p[i].start)>eps)--R;
while(R-L>1&&cross(p[i].endi-p[i].start,Cross[L+2]-p[i].start)>eps)++L;*/
while(R-L>1&&cross(p[i].endi-Cross[R],p[i].start-Cross[R])>eps)--R;
while(R-L>1&&cross(p[i].endi-Cross[L+2],p[i].start-Cross[L+2])>eps)++L;
stacki[++R]=p[i];
if(R-L>1)Cross[R]=findCross(stacki[R-1],stacki[R]);
}
//while(R-L>1&&cross(stacki[L+1].endi-stacki[L+1].start,Cross[R]-stacki[L+1].start)>eps)--R;
while(R-L>1&&cross(stacki[L+1].endi-Cross[R],stacki[L+1].start-Cross[R])>eps)--R;
//Cross[R+1]=findCross(stacki[L+1],stacki[R]);++R;
}
struct node{
stain start,endi;
double k,b;
bool operator <(const node &x)const{
return start.x>n;
for(int i=1;i<=n;i++)cin>>a[i].x;
for(int i=1;i<=n;i++)cin>>a[i].y;
for(int i=1;i