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}
\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)
\alpha=atan2(y,x)
\[记得打头文件 **`#includeh=\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})