20230721-计算几何-526互联

20230721

向量

向量的加减，直接\(A.x \pm B.x,A.y \pm B.y\)

struct Point{
  double x,y;
  Point(double a=0,double b=0){x=a,y=b;}
  Point operator + (Point A){return Point(x+A.x,y+A.y);}
  Point operator - (Point A){return Point(x-A.x,y-A.y);}
};

向量的夹角，记作\(<a,b>\)
向量的模长，记作\(|\vec a|\)
顾名思义，\(|\vec a|=\sqrt{x^2+y^2}\)
代码上可以用点积来实现
```
double Length(Point A){return sqrt(Dot(A,A));}
```
向量的点积
\(\vec a \cdot \vec b=|\vec a||\vec b| \cos<a,b>=a.x \times b.x+a.y \times b.y\)
几何意义：\(\vec a\)在\(\vec b\)上的投影长度乘上\(\vec b\)的模长
应用：
若\(\vec a \cdot \vec b \gt 0\)，则\(\vec a\)与\(\vec b\)的夹角为锐角
若\(\vec a \cdot \vec b = 0\)，则\(\vec a\)与\(\vec b\)的夹角为直角
若\(\vec a \cdot \vec b \lt 0\)，则\(\vec a\)与\(\vec b\)的夹角为钝角
```
double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
```
向量的叉积
\(\vec a \times \vec b=|\vec a||\vec b|\sin<a,b>=a.x \times b.y - b.x \times a.y\)
几何意义：以\(\vec a\)与\(\vec b\)为邻边形成的平行四边形的有向面积，符号与\(\sin <a,b>\)相同
应用：
若\(\vec a \times \vec b=0\)则\(\vec a\)与\(\vec b\)共线
若\(\vec a \times \vec b \gt 0\)则\(\vec a\)在\(\vec a\)的逆时针方向
若\(\vec a \times \vec b \lt 0\)则\(\vec a\)在\(\vec a\)的顺时针方向
两向量所组成的三角形面积为其叉积除以二
```
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
```

点与线的距离
与直线：面积除以底边长
与射线或线段：判断垂足是否在线段上（用点积判断夹角）
垂足：点积除以模长得到投影长度，用投影长度之比来算

//求m到线段ab的最短距离的点
vec x=m-a,y=m-b,z=b-a;
if(x==z){ans=0.0,res=m;return;}
if(cmp(Dot(x,z))<0) tmp=a;//在a时取到最小
else if(cmp(Dot(y,z))>0) tmp=b;
else{
  xx1=Dot(x,z)/Lenth(z);
  xx2=-1.0*Dot(y,z)/Lenth(z);
  tmp=a+z*(xx1/(xx1+xx2));//求垂足
}
if(cmp(Lenth(tmp-m)-Lenth(m-res))<0) res=tmp;

UVA10263 Railway

题目描述

传送门
点与线的距离

Solution

求点到线段的距离即可
注意误差问题很重要！
cmp函数很重要！！！

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-5;
int n;
double ans=0,x,dis,xx1,xx2;
struct vec{
  double x,y;
  vec(double a=0,double b=0){x=a,y=b;}
  vec operator +(const vec &a) const{return vec(x+a.x,y+a.y);}
  vec operator -(const vec &a) const{return vec(x-a.x,y-a.y);}
  vec operator *(double k)const{return vec(k*x,k*y);}
  bool operator ==(const vec &a)const{return (x==a.x&&y==a.y)?1:0;}
}m,st,a,b,tmp,res;
double Dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
double Cross(vec a,vec b){return a.x*b.y-b.x*a.y;}
double Lenth(vec a){return sqrt(Dot(a,a));}
int cmp(double p){return p<-eps?-1:(p>eps?1:0);}

void solve(vec m,vec a,vec b){
  vec x=m-a,y=m-b,z=b-a;
  if(x==z){ans=0.0,res=m;return;}
  if(cmp(Dot(x,z))<0) tmp=a;
  else if(cmp(Dot(y,z))>0) tmp=b;
  else{
	xx1=Dot(x,z)/Lenth(z);
	xx2=-1.0*Dot(y,z)/Lenth(z);
	tmp=a+z*(xx1/(xx1+xx2));
  }
  if(cmp(Lenth(tmp-m)-Lenth(m-res))<0) res=tmp;	
}

int main(){
  /*2023.7.21 H_W_Y UVA10263 Railway 计算几何*/ 
  while(scanf("%lf",&m.x)!=EOF){
  	ans=(double)1000000000;
  	scanf("%lf%d%lf%lf",&m.y,&n,&st.x,&st.y);a=st;
  	for(int i=2;i<=n+1;i++){
  	  scanf("%lf%lf",&b.x,&b.y);
      solve(m,a,b);a=b;	
	}
	solve(m,st,a);
	printf("%.4lf\n%.4lf\n",res.x,res.y);
  }
  return 0;
}

凸包

P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

题目描述

传送门

Solution

凸包模板

#include <bits/stdc++.h> 
using namespace std;

const int maxn=1e5+10;
int n,tp=0;
struct Point{
  double x,y;
  Point(double a=0,double b=0){x=a,y=b;}
  Point operator + (Point A){return Point(x+A.x,y+A.y);}
  Point operator - (Point A){return Point(x-A.x,y-A.y);}
}a[maxn],st[maxn];

double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
double Length(Point A){return sqrt(Dot(A,A));}

bool cmp1(Point A,Point B){
  if(A.x!=B.x) return A.x<B.x;
  return A.y<B.y;
}

bool cmp2(Point A,Point B){
  double des=Cross(A-a[1],B-a[1]);
  if(des!=0) return des>0;
  return Length(A-a[1])<Length(B-a[1]);
}

int main(){
  /*2023.2.6 hewanying P2742 圈奶牛 凸包*/ 
  scanf("%d",&n);tp=0;
  for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
  if(n==1){printf("0.00\n");return 0;}
  if(n==2){printf("%.2f\n",fabs(Length(a[1]-a[2])));return 0;}
  sort(a+1,a+n+1,cmp1);
  sort(a+2,a+n+1,cmp2);
  st[++tp]=a[1];st[++tp]=a[2];st[++tp]=a[3];
  for(int i=4;i<=n;i++){
  	while(tp>=2){
  	  double des=Cross(st[tp]-st[tp-1],a[i]-st[tp]);
	  if(des<=0) tp--;
	  else break;	
	}
	st[++tp]=a[i];
  }
  double s=0;
  for(int i=1;i<=tp;i++) s+=Length(st[i%tp+1]-st[i]);
  printf("%.2f\n",s);
  return 0;
}