2019银川网络赛 Rolling The Polygon 简单的计算几何

Bahiyyah has a convex polygon with n vertices P0,P1,……,Pn−1 in the counterclockwise order. Two vertices with consecutive indexes are adjacent, and besides, P0 and Pn−1 are adjacent. She also assigns a point Q inside the polygon which may appear on the border.Now, Bahiyyah decides to roll the polygon along a straight line and calculate the length of the trajectory (or track) of point Q.To help clarify, we suppose Pn P0,Pn1 P1 and assume the edge between P0 and P1 is lying on the line at first.At that point when the edge between Pi−1 and Pi lies on the line, Bahiyyah rolls the polygon forward rotating the polygon along the vertex Pi until the next edge (which is between Pi and Pi1 ) meets the line. She will stop the rolling when the edge between Pn and Pn1 (which is same as the edge between P0and P1 ) meets the line again.输入The input contains several test cases, and the first line is a positive integer T indicating the number of test cases which is up to 50.For each test case, the first line contains an integer n (3≤n≤50) indicating the number of vertices of the given convex polygon. Following n lines describe vertices of the polygon in the counterclockwise order. The i-th line of them contains two integers xi−1 and yi−1 , which are the coordinates of point Pi−1 . The last line contains two integers xQ and yQ , which are the coordinates of point Q.We guarantee that all coordinates are in the range of -103 to 103 , and point Q is located inside the polygon or lies on its border.输出For each test case, output a line containing Case #x: y, where x is the test case number starting from 1, and y is the length of the trajectory of the point Q rounded to 3 places. We guarantee that 4-th place after the decimal point in the precise answer would not be 4 or 5.样例输入复制样例数据4 4 0 0 2 0 2 2 0 2 1 1 3 0 0 2 1 1 2 1 1 5 0 0 1 0 2 2 1 3 -1 2 0 0 6 0 0 3 0 4 1 2 2 1 2 -1 1 1 0样例输出Case #1: 8.886 Case #2: 7.318 Case #3: 12.102 Case #4: 14.537提示The following figure is the the trajectory of the point Q in the fi rst sample test case.虽然是原题但是自己比赛的时候没做出来。主要因为当时读错题了。。。赛后理解对题意之后这个题竟然还看个四十多分钟总结一下吧。题意 给定一个凸多边形和多边形内的一点按逆序给出。问这个多边形绕着自己的边旋转一周这个点走过的距离。注意是绕着自己的边我以为是绕着x或y轴所以一直不知道如何下手。思路先看下画的图吧是第二个样例的图可以很清晰的发现就是转了一个角度这个角度就是它所对应角的补角互为补角是相加180度高中的数学都快忘了哈哈哈。然后用余弦定理求acos值就可以了对应每条边注意i1和in时对应的边的小细节。然后用扇形的弧度公式求解长度就可以了。S长度R半径*acos角度#includebits/stdc.h #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #pragma GCC optimize(2) #define PI 3.1415926 double esp1e-10; using namespace std; const int maxx1e415; struct stu { double x,y; double juli;//半径 }A[maxx]; int main() { ll i,j,k,t,x; ll n,m; scanf(%lld,t); for(int p1;pt;p) { scanf(%lld,n); double changdu0; for(i1;in1;i) { scanf(%lf%lfd,A[i].x,A[i].y); } for(i1;in;i) { A[i].juli(A[i].x-A[n1].x)*(A[i].x-A[n1].x)(A[i].y-A[n1].y)*(A[i].y-A[n1].y); A[i].julisqrt(A[i].juli); } A[0].xA[n].x; A[0].yA[n].y; A[n1].xA[1].x; A[n1].yA[1].y; for(i1;in;i) { double a1(A[i].x-A[i1].x)*(A[i].x-A[i1].x)(A[i].y-A[i1].y)*(A[i].y-A[i1].y); double b1(A[i].x-A[i-1].x)*(A[i].x-A[i-1].x)(A[i].y-A[i-1].y)*(A[i].y-A[i-1].y); double c1(A[i-1].x-A[i1].x)*(A[i-1].x-A[i1].x)(A[i-1].y-A[i1].y)*(A[i-1].y-A[i1].y); a1sqrt(a1);b1sqrt(b1);c1sqrt(c1); double jiaoduacos((a1*a1b1*b1-c1*c1)/(2*a1*b1)); changdu(acos(-1.0)-jiaodu)*(A[i].juli);// 弧度公式 } printf(Case #%d: %.3lf\n,p,changdu); } return 0; }补题不重要重要的是回顾一下这样的小知识以后别蠢蠢的连这种水题都做不出来。。。