[SGU120 Archipelago]【平面几何】【向量旋转】

【题目链接】http://acm.sgu.ru/problem.php?contest=0&problem=120

【题目大意】

给定一个N边形，这个N边形上的点都被按顺时针顺序标号为1,2,3…。然后给出标号为m1和m2的点的坐标，最后按标号顺序输出这个多边形所有的点。

【算法分析】

大概思路是先算出中心，然后用向量一直转，就能得到所有的点。

我们先连接m1,m2两个点得到线段L，然后作这条线段的中垂线L’。然后可以很轻松算出图中的角α的值（就是pi/n*(abs(m1-m2))）。然后搞到0~pi之间就可以了。然后我们知道中心点Mid到L的距离d。

然后对向量m1->m2旋转个90°/270°，再把长度调成d。就可以得出中心点的位置了。

当然，如果abs(m1-m2)*2==n要特判一下。因为取不到tan。。。= =，应该有更好的方法。

然后可以得出中心Mid的坐标。然后构造Mid->a[m1]的向量，然后把这个向量每次旋转2*pi/n，就可以了得出所有坐标了噢。

^_^

【关于向量旋转】

学过极坐标的话。。。这个太简单了。

下面推导一下~~

对于向量(x,y)，如果要顺时针旋转的角度β的话，那么这样弄。

转化为极坐标:

x=L*cos(α)

y=L*sin(α)

然后旋转以后变成

x=L*cos(α-β)=L*cos(α)*cos(β)+L*sin(α)*sin(β)

y=L*sin(α-β)=L*sin(α)*cos(β)-L*cos(α)*sin(β)

然后变回直角坐标系

x=x*cos(β)+y*sin(β)

y=y*cos(β)-x*sin(β)

然后就完成了旋转

【CODE】

C++ CODE   :SGU120 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 #include