这个题我开始一读,好懵逼哦;这个多边形怎么转呢?
就是这句话;
我才读懂了是什么意思:
意思就是这个意思:给定三角形,然后以最低的一条边,旋转,然后转到和第一条边重合的时候就停下来,然后算这个弧长总和;我开始真没发现什么规律,后来我的队友写了写三角形,忽然发现这个有这个规律:
那么一个弧长对应的L就是
,所以我只需要求所有的角度就行,然后发现角度可以用向量来计算;距离就很简单了,可以直接枚举计算;
比如这个多边形:
角度就直接可以计算了;所以最后我们可以推出一个公式,结果就是求:
这里的d是每个点到Q点的距离;所以可以这样计算;(因为你多写几个就会发现,这个求弧长,其实就是求对应角度与对应d的乘积之和);
但是我知道这样写了;但是我不知道怎么求角度;后来看了一下题目说是逆时针给出的点,咦,那就简单了涩,直接挨着求不就完了吗?因为这个问题我还想了半天,我也是。。。。。。。;
然后直接每个点求到Q点的距离,然后对应的每个内角的补角,然后扫一遍算一次就可以了;只不过注意边和角对应的下标关系;
也就是:
所以最后就是AC了;这个题主要是能找出这个角的关系,然后向量计算就行了;注意这里不需要去讨论点在边上的问题;因为只要在凸多边形内(包含边界)就OK了;
所以AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double Qx,Qy;
double PI=acos(-1);
struct Point{//存点
double x,y;
Point(){}
Point(double xx,double yy):x(xx),y(yy){}
}p[100],V[100];//第一个p用来记录点,第二个V用来存向量(因为是两个点形成一个向量)
double Dot(Point A, Point B){//算向量
return A.x*B.x + A.y*B.y;
}
double Length(Point A){//算向量的模
return sqrt(Dot(A, A));
}
double Angle(Point A, Point B){//算上面分析的角度
return acos(Dot(A, B) / Length(A) / Length(B));
}
double Dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//算两点间距离
}
double dis[100];//存每个点到Q点的距离
int main(){
int T;
scanf("%d",&T);
int g=1;
while(T--){
int n;
scanf("%d",&n);
for(int i=0;i<n+1;i++){
if(i==n)scanf("%lf %lf",&Qx,&Qy);
else scanf("%lf %lf",&p[i].x,&p[i].y);
}
int num=0;
for(int i=1;i<n;i++){
dis[num++]=Dis(p[i-1].x,p[i-1].y,Qx,Qy);//存距离///下标从0开始
V[i].x=p[i].x-p[i-1].x;//根据向量运算,然后求A-》B的向量
V[i].y=p[i].y-p[i-1].y;
}
V[n].x=p[0].x-p[n-1].x;//求最后一组向量
V[n].y=p[0].y-p[n-1].y;
dis[num++]=Dis(p[n-1].x,p[n-1].y,Qx,Qy);//求最后一个到Q点的距离
double ans=0;
for(int i=1;i<n;i++){//这就是上面推的公式
ans+=Angle(V[i],V[i+1])*dis[i];
}
ans+=Angle(V[n],V[1])*dis[0];//注意,这里需要算第一个向量和最后一个向量,就这里我wa了一次;唉.......
printf("Case #%d: %0.3lf\n",g++,ans);
}
return 0;
}