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,Pn+1 = 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 Pi+1 ) meets the line. She will stop the rolling when the edge between Pn and Pn+1 (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值就可以了，对应每条边，注意i==1和i==n时对应的边的小细节。然后用扇形的弧度公式求解长度就可以了。S（长度）=R（半径）*acos（角度）
#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #pragma GCC optimize(2) #define PI 3.1415926 double esp=1e-10; using namespace std; const int maxx=1e4+15; 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 p=1;p<=t;p++) { scanf("%lld",&n); double changdu=0; for(i=1;i<=n+1;i++) { scanf("%lf%lfd",&A[i].x,&A[i].y); } for(i=1;i<=n;i++) { A[i].juli=(A[i].x-A[n+1].x)*(A[i].x-A[n+1].x)+(A[i].y-A[n+1].y)*(A[i].y-A[n+1].y); A[i].juli=sqrt(A[i].juli); } A[0].x=A[n].x; A[0].y=A[n].y; A[n+1].x=A[1].x; A[n+1].y=A[1].y; for(i=1;i<=n;i++) { double a1=(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 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[i+1].x)*(A[i-1].x-A[i+1].x)+(A[i-1].y-A[i+1].y)*(A[i-1].y-A[i+1].y); a1=sqrt(a1);b1=sqrt(b1);c1=sqrt(c1); double jiaodu=acos((a1*a1+b1*b1-c1*c1)/(2*a1*b1)); changdu+=(acos(-1.0)-jiaodu)*(A[i].juli);// 弧度公式 } printf("Case #%d: %.3lf\n",p,changdu); } return 0; }