信息学集训队作业0033-dream

题目0033–Dream(几何美梦)题目来源：Ural推荐者：金恺英文原文GeometricaldreamsTimeLimit:5secondMemoryLimit:1000KProblemThereisapolygonn(theverticesarenumberedintheclockwiseorder).Oneachsideanisoscelestriangleisbuiltontheoutersideofthepolygon,andangle.Here.Thesetofanglessatisfiesaconditionthatthesumofanglesinanyofitsnonemptysubsetsisnotaliquotto360degrees.Youaregiven,co-ordinatesofverticesandangles(measuredindegrees).Writeaprogramwhichrestoresco-ordinatesofthepolygonvertices.InputThefirstlineofaninputcontainsaninteger.Thenextlinescontainpairsofrealnumberswhichareco-ordinatesofpoints.Andthelastlinesofthefileconsistofdegreevaluesofangles.OutputTheoutputfileshouldcontainlinesofpairsofcoordinatesofthepointsSampleinputSampleinput3023320909090Sampleoutput111331中文翻译时间限制：3秒存储器限制：1000K问题有一个多边形(顺时针给出顶点号)。在多边形的每一条边的外边构造一个等腰三角形，角。这里。这些角满足条件：任何这些角的非空子集的和都不能整除360度。给出，顶点的坐标和角(标准角度)。写一个程序恢复多边形顶点的坐标。输入一个整数。接下来的行包括的坐标有序实数对。最后的行是角的度数。输出每个点的坐标。三、初步讨论情况方奇设多边形顶点坐标，列方程组，解方程组，比较简单的一道几何题。张云亮解方程，把整个坐标系看成一个复平面(x,y)变为x+yi,x+yi逆时针旋转a度即为(x+yi)*(cosa+isina),之后解方程即可，得出第一个点的x,y,值，其余迎刃而解。刘才良用复数，然后解方程就行了。设Zi是对应辐角为i的单位向量，A2=(A1-M1)*Z1+M1，A3=(A2-M2)*Z2+M2，…An+1=A1，联立可解出A1，再推出其他的点。张宁这道题目，只要设出第一个点的坐标，然后可以依次解出其余n-1个点的坐标，并且需满足第n+1个点与第一个点重合，这样就可以解出所有的点的坐标许智磊假设P1坐标为(x1,y1)，就可以把余下的点用x1和y1来表示，最后又可以表示出P1=(f(x1),g(y1)，联立x1=f(x1)和y1=g(y1)可以解出x1和y1，也就可以确定原多边形了。伍昱列方程。设第一个点坐标(x,y)，根据题目条件可以推出第二个点的坐标(关于x,y的一次式)再继续推下去直到推回第一个点。此时可以得到关于x,y的一次方程。林希德设顶点1的坐标为(x1,y1)，将x和y看成已知常量；然后求出顶点1绕M1旋转角度a1后的位置（x2,y2），即顶点2；接着求出顶点2绕M2旋转角度a2后的位置（x3,y3），即顶点3……最后求出顶点n绕Mn旋转角度an后的位置（xn+1,yn+1），即顶点1。这样顶点1的坐标值有（x1,y1）和（xn+1,yn+1）两个表达式，两表达式组成一方程，解之即可。王知昆设A1的坐标为(x0,y0)，通过题目所给的参数，可以得到A2,A3,…………An的坐标（关于x0，y0的式子），最后，由An的坐标可以得到两个关于x0，y0的方程，方程的解就是A1的坐标。疑问：是否一定有唯一解，和“任何这些角的非空子集的和都不能整除360度”有什么关系。刘一鸣取多边形的顶点A1，设坐标为（x,y）。然后就可以根据A1所在的一个等腰三角形的顶点坐标和顶角的大小求出三角形底边上的另一个点A2。由A2点又可以求出另外一个点，这样反复下去可以用x,y表示出A1的坐标。于是，就分别构造了一个关于x和y的方程。解出x和y，就求出了A1。然后就依次求出A2，A3……。问题就解决了。何林这个题目我感觉是解方程。设A1的坐标是(x,y)。将向量M1A1绕M1逆时针旋转a1的角度后，得到的A1’就是A2，于是A2的坐标就可以用关于x,y的一次式表示出来。类似的用A2表示A3，A3表示A4，……，最后又通过An推回来到A1。如此，通过推回来的式子和(x,y)联立一个方程，解之便可得到答案。关键是：如果列出的方程出现多解或者无解该怎么办？题目有一个条件“任何这些角的非空子集的和都不能整除360度。”我没有用到。我估计这个条件就能保证方程必然有唯一解答，不过仅仅是一个猜想罢了。至于是不是真的如此，希望大家能继续讨论。饶向荣解方程，设第一个坐标为X,Y，可推出第二个点的坐标关于X,Y的表达式，然后推出第三点关于X,Y的表达式….直到最后第N+1点的坐标值必须等于X,Y，列出关于横纵坐标两个方程，求解即可。如果第一个点的坐标为X,Y，而M1坐标为(a,b)，角为α，那么第二个点的坐标的表达式为，依此类推。时间复杂度为O(N)，空间复杂度为O(N)。金恺对不起大家，我弄错了：这不是构造题，而是解方程。但是有一个条件不知道是什么意思：任何这些角的非空子集的和都不能整除360度。难道这是有解的充分条件吗？做法：假设第一个点的坐标为（x,y），则第二个点的坐标可以根据A1、α1的值用(ax+k,by+l)表示出来（其中a、b、k、l为常数），然后第三个点也可类似的表示成(a’(ax+k)+k’,b’(by+l)+l’)即(a2x+k2,b2y+l2)，同样的，第N个点也可表示成(aNx+kN,bNy+lN)，根据AN、αN又可求出第一点的坐标为(a1x+k1,b1y+l1)，易知：a1x+k1=x，b1y+l1=y，所以：、。刘汝佳：我们从刘才良的方程讨论（点都看成复数）。A2=(A1-M1)*Z1+M1=A1Z1–(Z1–1)M1，A3=A2Z2–(Z2–1)M2=A1Z1Z2–(Z1-1)Z2M1–(Z2-1)M2A4=A3Z3–(Z3–1)M3=A1Z1Z2Z3–(Z1-1)Z2Z3M1–(Z2-1)Z3M2-(Z3-1)M3到最后，有A1=A1Z1…Zn–(Z1-1)Z2…ZnM1–(Z2-1)Z3…ZnM2-…-(Zn-1)Mn。移项，有：(Z1Z2…Zn-1)A1=(