Codeforces gym102222 B.Rolling The Polygon 凸包/余弦定理

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

有一个不保证凸的多边形，让你滚一圈，计算某点滚出的轨迹多长。

题解：

求出凸包后，以每个点为转轴，转轴到定点的距离为半径，用余弦定理计算圆心角，计算弧长。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int main()

{

    int t,case1=;

    cin>>t;

    while(t--)

    {

        case1++;

        int n;

        cin>>n;

        int x[],y[];//贮存坐标

        for(int i=;i<=n;i++)

        {

            cin>>x[i]>>y[i];

        }

        int xx,yy;

        cin>>xx>>yy;

        double dis[];

        for(int i=;i<=n;i++)

        {

            dis[i]=(x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy);

            //cout<<dis[i]<<endl;

        }

        //cout<<endl;

        double ankle[];

        for(int i=;i<=n;i++)

        {

            double t1,t2,t3;

            if(xx==x[i]&&yy==y[i])

            continue;

            if(i==)

            {

                t1=sqrt((x[]-x[])*(x[]-x[])+(y[]-y[])*(y[]-y[]));

                t2=sqrt((x[n]-x[])*(x[n]-x[])+(y[n]-y[])*(y[n]-y[]));

                t3=sqrt((x[n]-x[])*(x[n]-x[])+(y[n]-y[])*(y[n]-y[]));

            }

            else if(i==n)

            {

                t1=sqrt((x[n]-x[])*(x[n]-x[])+(y[n]-y[])*(y[n]-y[]));

                t2=sqrt((x[n]-x[n-])*(x[n]-x[n-])+(y[n]-y[n-])*(y[n]-y[n-]));

                t3=sqrt((x[n-]-x[])*(x[n-]-x[])+(y[n-]-y[])*(y[n-]-y[]));

            }

            else

            {

                t1=sqrt((x[i+]-x[i])*(x[i+]-x[i])+(y[i+]-y[i])*(y[i+]-y[i]));

                t2=sqrt((x[i]-x[i-])*(x[i]-x[i-])+(y[i]-y[i-])*(y[i]-y[i-]));

                t3=sqrt((x[i-]-x[i+])*(x[i-]-x[i+])+(y[i-]-y[i+])*(y[i-]-y[i+]));

            }

            //cout<<t1<<" "<<t2<<" "<<t3<<" ";

            ankle[i]=acos((t1*t1+t2*t2-t3*t3)/(*t1*t2));

            //cout<<ankle[i]<<" ";

            //cout<<endl;

        }

        double l=;

        for(int i=;i<=n;i++)

        {

            l+=sqrt(dis[i])*(acos(-1.0)-ankle[i]);

        }

        printf("Case #%d: %.3lf\n",case1,l);

    }

    return ;

}