本来之前很早就在某czy 的计算⼏何专题上了解了计算⼏何的⼀些⼩知识。
然⽽当时太年轻，学不懂。
到现在，突然来了热⾎。翻了必修四⼀遍⼜⼀遍，百度百科也是看了⼀遍⼜⼀遍。
最终有所成，但是没复习，导致现在忘了许多。
于是现在开始好好打篇博客来权当复习。
当然，也顺便学习了⼀下别⼈初⼀就会的东东。
这个东东很简单，指具有⼤⼩和⽅向的量。就是⼀个类似于箭头的线 （不是♂）
这个东东⾼中讲到物理的正交分解之类的就知道是长什么样的了。
其实信息学对于这个研究⼤多只需要⼆维平⾯以及⼀些基本运算。
书写时在字母顶上加⼀⼩箭头“→”。如果给定向量的起点（A ）和终点（B ），可将向量记作→AB AB 。
接下来就有⼀个⽐较有⽤的东东：模长：表⽰为|a|，意思是⼀个向量的长度。
其他似乎没有了。
接下来就讲讲这些运算。
当然，向量可以表⽰为⼀个坐标(x,y)
原谅我盗个图：
在这个图中我们清晰地看到，两个向量相加就相当于两个向量组成的平⾏四边形的对⾓线。
→A A 表⽰为(x1,y1)→B B
表⽰为(x2,y2)
则计算表⽰为→A +→B =→C A
+B
=C
坐标表⽰为：(x1+x2,y1+y2)这个其实很好理解。
我们可以知道，⼀个向量→A A
取反即表⽰为→
−A −A
那么就可以把它⽤加法来弄即可。表⽰为⼀个向量乘上⼀个常数。
意思就是⼀个向量变长或缩短或取相反。
表⽰为：→A ∗⼀个常数A
∗(⼀个常数)
注意⼩⼼常数为0的情况。⾸先，点积是给出两个向量，→
A A
、→B B 然后求出⼀个定值（不是向量）
表⽰为→
A
⋅→
B
A
⋅
B ()
这个有两种定义：
代数定义
→A ⋅→B =x 1∗x 2+y 1∗y 2A
⋅B
=x1∗x2+y1∗y2
⼏何定义
看到⼀个图：
我们可以从中得到：
→A ⋅→B =∣→A ∣∗∣→B ∣∗cos θ夹⾓⼤⼩A
⋅B
=∣A
∣∗∣B
∣∗cos θ(夹⾓⼤⼩)
也就是图中的投影*原长
⾄于上述两种定义如何互相转化，有很多⽅法证明
这⾥有⼀个我⽐较喜欢的做法：
⾸先，我们发现两个向量可以组成⼀个三⾓形。
我们设第三边是→C C
则根据余弦定理得：∣→C ∣2=∣→A ∣2+∣→B ∣2−2∗∣→B ∣∗∣→
A ∣∗cos θ∣C
∣2=∣A
∣2+∣B
∣2−2∗∣B
∣∗∣A
∣∗cos θ
移⼀下项：∣→B ∣∗∣→A ∣∗cos θ=
∣A ∣2+∣B ∣2−∣C ∣22∣B
∣∗∣A
∣∗cos θ=2∣A
广谱抗菌素
∣2+∣B
∣2−∣C
∣2
拆掉后⾯的向量模长，得∣→B ∣∗∣→A ∣∗cos θ=
x 12+y 12+x 22+y 22−x 1−x 2)2−y 1−y 2)22∣B
∣∗∣A ∣∗cos θ=2x12+y12+x22+y22−(x1−x2)2−(y1−y2)2
于是就可以证明啦~~
当然，可以推导到3维的去。然⽽信息学⼤多只讨论2维。这个其实就是求两个向量围成的平⾏四边形的有向⾯积。
有向⾯积是什么呢？其实就是在左⼿向为正，右⼿向为负。
表⽰：→B ×→A 或→B ∧→
A B
×A
或B
∧A
定义——⼀样有两个
⼏何定义
→B ×→A =∣→B ∣∗
∣→A ∣∗sin θB
×A
=∣B
∣∗∣A
∣∗sin θ（也就是四边形⾯积）
代数定义
→A ×→B =x 1∗y 2−y 1∗x 2A ()((
×B
=x1∗y2−y1∗x2
葡萄架势证明？
似乎是类似于上⾯的。
于是这⾥就介绍完⼤部分的向量运算了。
（lj浏览器刚刚打的全部都没有保存，⽓死偶类）
当然，我们当然可以在中考数学⾥⽤这个向量，会有70%的⼏率⽼师看不懂⽽打×。
uses math;
type
new=record
x,y,jj,jl:extended;
kind,bh:longint;
end;
new1=record
x,y,r:extended;
end;
new2=record
a,b,c:extended;
end;
var
i,j,k,l,n,m,gs,t,num,now:longint;
cir:array[1..250000] of new1;
jd:new;
a,b,r,x,y,xx,yy:extended;
spot:array[1..250000] of new;
dl:array[1..250000] of longint;
fx:array[1..4,1..2] of longint=((-1,1),(-1,-1),(1,-1),(1,1));
dt,nx,ny,answer:extended;
tir:new2;
function dist(x1,y1,x2,y2:extended):extended;
begin
exit(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
end;
function judge(ax,ay,bx,by,cx,cy:extended):extended;
begin
exit(ax*by+cx*ay+bx*cy-cx*by-bx*ay-ax*cy);
end;
procedure con_bag;
var
i,j,k,up:longint;
x,y,miny,minx,a,b,c:extended;
procedure qsort(l,r:longint);
var
i,j:longint;
m,m1:extended;
k:new;
begin
i:=l;j:=r;
m:=spot[(l+r) div 2].jj;
m1:=spot[(l+r) div 2].jl;
repeat
while (spot[i].jj<m) or ((spot[i].jj=m) and (spot[i].jl<m1)) do inc(i);
透水混凝土施工
while (spot[j].jj>m) or ((spot[j].jj=m) and (spot[j].jl>m1)) do dec(j);
if i<=j then
begin
k:=spot[i];
电动雕刻刀
spot[i]:=spot[j];
spot[j]:=k;
脚底按摩鞋
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if r>i then qsort(i,r);
end;
begin
gs:=0;
miny:=maxlongint;
minx:=maxlongint;
for i:=1 to num do
begin
if (spot[i].y<miny) or ((spot[i].y=miny) and (spot[i].x<minx)) then
begin
miny:=spot[i].y;
minx:=spot[i].x;
j:=i;
end;
end;
x:=spot[j].x;
y:=spot[j].y;
for i:=1 to num do
begin
spot[i].x:=spot[i].x-x;
spot[i].y:=spot[i].y-y;
if spot[i].y=0 then spot[i].jj:=0
else
if spot[i].x=0 then spot[i].jj:=90
else
if spot[i].x<0 then spot[i].jj:=arctan(spot[i].y/spot[i].x)*(180/pi)+180
else spot[i].jj:=arctan(spot[i].y/spot[i].x)*(180/pi);
spot[i].jl:=dist(0,0,spot[i].x,spot[i].y);
end;
qsort(1,num);
up:=2;
dl[1]:=1;
dl[2]:=2;
for i:=3 to num do
begin
while (up>1) and (judge(spot[dl[up-1]].x,spot[dl[up-1]].y,spot[dl[up]].x,spot[dl[up]].y,spot[i].x,spot[i].y)<=0) do dec(up);
if (spot[dl[up]].x<>spot[i].x) or (spot[dl[up]].y<>spot[i].y) then
begin
inc(up);
dl[up]:=i;
end;
end;
inc(up);
dl[up]:=dl[1];
answer:=0;
for i:=2 to up do
begin
谷氨酰胺合成酶
answer:=answer+dist(spot[dl[i]].x,spot[dl[i]].y,spot[dl[i-1]].x,spot[dl[i-1]].y);
end;
writeln(answer+2*pi*r:0:2);
end;
begin
readln(n);
readln(a,b,r);
a:=a/2-r;
b:=b/2-r;
m:=0;
for i:=1 to n do
begin
readln(x,y,dt);
for j:=1 to 4do
begin
xx:=fx[j,1]*a;
yy:=fx[j,2]*b;
inc(m);
cir[m].x:=x+yy*cos(dt)-xx*sin(dt);
cir[m].y:=y+xx*cos(dt)+yy*sin(dt);
cir[m].r:=r;
inc(num);
spot[num].x:=cir[m].x;
spot[num].y:=cir[m].y;
end;
end;
n:=m;
con_bag;
end.
这个很⾼⼤上，其实思路很简单。
⾸先：这个东东是什么？
我们想象现在有⼀张A4⽩纸，现在我们⼀⼑下去分成两⽚纸，那么其中⼀⽚即为半平⾯。
那么半平⾯交就是很多半平⾯相交的部分。
似乎这个东东很像线性规划⾥的知识。
先不理了。
那么这个有什么⽤？
⼀个古⽼的问题——
给定⼀个任意的多边形，⼀个⼈站在⾥⾯，如果他可以看见这个多边形任意⼀个⾓落（所有边都可以看到不被阻挡），那么这个点是⼀个核求核的⾯积。
那么我们从这个问题下⼿。
求这个n边形的核？
⾸先我们逆时针弄出n个向量（类似）
我们再按照极⾓排序。
然后关键⼀步——
假设现在是在⼀张⽩纸上。
编号从⼩到⼤来做，每次把当前向量的左⼿边保留，右⼿边删去。
第⼀步：
第⼆步：
多步以后
于是，中间⽩⾊部分的⾯积就是要求的⾯积了。
怎么得到？
不好求吗？
由于得到直线集合，那么相邻两个直线交点不是可以求吗？
直接⽤叉积求和即可。
优化？
极⾓排序时把相同的两个线保留左边的。
似乎优化不了多少。
但没关系，算法已经是O(n O(n log log n)n)的了
算法流程：
1、以逆时针为正⽅向，建边。(输⼊⽅向不确定时，可⽤叉乘求⾯积看正负得知输⼊的顺逆⽅向。)
2、极⾓排序。
3、⽤有两个端点的队列储存线段集合。（意思是⼀个⾸可以删，尾可以删的队列）
4、枚举判断⼀个直线加⼊后对半平⾯交的影响。(对队列的头部和尾部进⾏判断)
5、如果某条在队列中的直线已经对半平⾯交没有影响了，就从队列中删掉。
6、最后剩下的直线集合，即为最后要求的半平⾯交。
7、求⾯积
很简单对吧？
其实思想和凸包很像很像。
代码待更……
“旋转卡壳有⼗六样读法，你知道么？”
这个旋转卡壳是⼲什么的呢？
其实主要就是求出⼀个叫做对踵点的东东。
如果过凸包上的两个点可以画⼀对平⾏直线，使凸包上的所有点都夹在两条平
⾏线之间或落在平⾏线上，那么这两个点叫做⼀对对踵点。
其实就是下图：
两个平⾏红线交于凸包另个点。这两个点即为对踵点。
当然，下⾯这种情况也是：
四个点也是⼀样的，就不画了。
求出来了有什么⽤呢？
我们可以惊讶地发现，如果要求⼀个凸多边形的直径（也就是最长的边）
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议