15011418730 LV 7 @ 2025-8-24 21:58:25

自动搬运

来自洛谷，原作者为

	Wy12121212 **

搬运于2025-08-24 21:58:25，当前版本为作者最后更新于2018-03-10 19:30:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

萃香的新年宴会第二题题解#2封兽鵺的激光游戏

by Wy12121212

题目链接

题意:平面上有一些凸多边形(不超过10个)，凸边形的边数均不超过五条，且开始时每个多边形会绕重心顺时针旋转90k°，现在你可以从某一给定点处引一条射线，射线碰到多边形一边时便会发生反射并删除这条边。

现在，你需要求出使反射总次数最接近k的最小出射角度(x轴正方向为0°，y轴正方向为90°)

本题做题难度: 省选？

本题思考难度: 普及+/提高-

考查知识点:计算几何，码力，细节处理

我先说一下吧，这道题确实挺神仙的，如果你实在不想写copy我的代码我也不反对，当然如果你执意要写我也很赞成qwq

看到这道题时你可能会蒙住，所以让我们一步一步来分析吧

1.求重心：

很简单的第一步，只要把多边形划分成很多个三角形逐个求就可以了(具体详解请百度，这里不会浪费太多篇幅)

这里就是第一步的代码啦:

//求重心
struct Point
{
    double x,y;
    Point(double x = 0, double y = 0) : x(x),y(y) {};
    void read()
    {
        scanf("%lf %lf",&x,&y);
    }
    Point operator - (const Point &a) const
    {
        return Point(a.x - x, a.y - y);
    }
}a[1010][10],g[1010],yuanxin[1010];

double cross(Point A, Point B)
{
    return A.x * B.y - A.y * B.x;
}

double area(Point a, Point b, Point c)
{
    Point A,B;
    A=b-a;
    B=c-a;
    return cross(A,B);
}

for(int _=1;_<=n;_++)
    {
        scanf("%d",&m);
        if(m==0)
        {
        	yuanxin[_].read();
        	scanf("%lf",&r[_]);
        }
        Point p0,p1,p2;
        double sum_x,sum_y,sum_area;
        p0.read();
        a[_][0].x=m;
        a[_][1]=p0;
        p1.read();
        a[_][2]=p1;
        sum_x=sum_y=sum_area=0.0;
        for(int i=2;i<m;i++)
        {
            p2.read();
            a[_][i+1]=p2;
            double tp=area(p0,p1,p2);
            sum_x+=(p0.x+p1.x+p2.x)*tp;
            sum_y+=(p0.y+p1.y+p2.y)*tp;
            sum_area+=tp;
            p1=p2;
        }
        Point G(sum_x/sum_area/3.0,sum_y/sum_area/3.0);
        g[_]=G;
    }

2.旋转:

好的我们现在有了每个多边形的重心g[i]，怎么将多边形旋转90k°呢？其实用初中全等之时便可以轻松解决

第二步的代码:

for(int i=1;i<=k;i++)
{
   double delx=a[_][j].x-g[_].x;
   double dely=a[_][j].y-g[_].y;
   a[_][j].x=g[_].x+dely;
   a[_][j].y=g[_].y-delx;
}

3.存储每条线段:

直接当成直线存下来就可以了，注意这里x,y,x1,y1是端点，a,b,c是解析参数

struct lazer
{
    double x,y;
    double a,b,c;
    double x1,y1;
    lazer(double a=0, double b=0,double c=0,double x=0,double y=0) : a(a),b(b),c(c),x(x),y(y) {};
};

            
if(j==a[_][0].x)
{
    xianduan[++cnt].x=a[_][j].x;
    xianduan[cnt].y=a[_][j].y;
    xianduan[cnt].x1=a[_][1].x;
    xianduan[cnt].y1=a[_][1].y;				
    xianduan[cnt].a=a[_][j].y-a[_][1].y;
    xianduan[cnt].b=-1*(a[_][j].x-a[_][1].x);
    xianduan[cnt].c=((a[_][j].x-a[_][1].x)*a[_][1].y)-(a[_][j].y-a[_][1].y)*a[_][1].x;			
}
else
{
    xianduan[++cnt].x=a[_][j].x;
    xianduan[cnt].y=a[_][j].y;
    xianduan[cnt].x1=a[_][j+1].x;
    xianduan[cnt].y1=a[_][j+1].y;	
    xianduan[cnt].a=a[_][j].y-a[_][j+1].y;
    xianduan[cnt].b=-1*(a[_][j].x-a[_][j+1].x);
    xianduan[cnt].c=((a[_][j].x-a[_][j+1].x)*a[_][j+1].y)-(a[_][j].y-a[_][j+1].y)*a[_][j+1].x;	
}

4.开始枚举每个角度射出激光:

用三角函数算出斜率和截距就可以了，这里我们采用端点-任一点的方式存储射线，但是有两点需要注意:

1.调用tan时要用i%180，不然会严重丢精

2.斜率不存在的时候要特判(写法较劣)

    for(double i=0;i<=360.0;i+=0.01)
    {
    	memset(shoot,0,sizeof(shoot));
        lazer st;
        st.x=x;
        st.y=y;
        double u=i;
        if(u>180)u-=180;
        if(u!=90&&u!=270)
        st.a=tan((u)*Pi/180),st.b=-1,st.c=(y-x*tan((u)*Pi/180));
        else
        {
            st.a=1;
            st.b=0;
            st.c=-1*x;
        }
        if(i==90||i==270)
        {
            if(i==90)st.x1=x,st.y1=y+10;
            else st.x1=x,st.y1=y-10;
        }
        else
        {
            if((i>=0&&i<=90)||(i>=270&&i<=360))
            st.x1=x+10,
            st.y1=(-st.c-st.a*st.x1)/(st.b);
            else
            st.x1=x-10,
            st.y1=(-st.c-st.a*st.x1)/(st.b);
        }
    }

5.判断射线与线段相交：

重头戏，当线段两个端点在射线异侧，且射线端点不位于交点与任一点之间的时候判断相交

Point inter(lazer a,lazer b)
{
    double y=((a.a*b.c-b.a*a.c)/(b.a*a.b-a.a*b.b));
    double x;
    if(a.a!=0)x=(-1*a.b*y-a.c)/a.a;
    else x=(-1*b.b*y-b.c)/b.a;
    Point intersp(x,y);
    return intersp;
}


bool updown(lazer a,Point b)
{
    if((-1*a.c-a.a*b.x)/a.b>b.y)return 1;
    if((-1*a.c-a.a*b.x)/a.b<b.y)return 0;
    return 2;
}

bool isinter(lazer a,lazer xd)
{
    Point tmp1(xd.x,xd.y);
    Point tmp2(xd.x1,xd.y1);
    if((updown(a,tmp1)^updown(a,tmp2))!=1)return 0;
    Point tmp3=inter(a,xd);
    if((a.x>=tmp3.x&&a.x<=a.x1)||(a.x<=tmp3.x&&a.x>=a.x1))return 0;
    //cout<<" "<<tmp3.x<<" "<<a.x<<" "<<a.x1<<endl;
    return 1;
}

6.直线反射：

取射线关于法线的对称点，然后将交点设为新的端点，对称点设为新的任一点即可

至于如何对称及反射后直线的方程最好手推一遍公式，代入就可以了


Point sym(Point a,lazer b)
{
    if(b.a==0)
    {
        Point tmp(a.x,(-1*b.c/b.b)-(a.y-(-1*b.c/b.b)));
        return tmp;
    }
    if(b.b==0)
    {
        Point tmp((-1*b.c/b.a)-(a.x-(-1*b.c/b.a)),a.y);
        return tmp;
    }
    lazer nl(b.b,-1*b.a,b.a*a.y-b.b*a.x);
    Point tmpp=inter(nl,b);
    double tmpx=2*tmpp.x-a.x;
    double tmpy=2*tmpp.y-a.y;
    Point tmp(tmpx,tmpy);
    return tmp;
}

lazer bounce(lazer a,lazer b)
{
    Point tmp1=inter(a,b);
    if((-1*a.a/a.b)*(-1*b.a/b.b)==-1)
    {
        lazer nl(a.a,a.b,a.c,tmp1.x,tmp1.y);
        return nl;
    }
    Point tmp2;
    tmp2.x=a.x,tmp2.y=a.y;
    Point tmp3;
    if(b.a!=0&&b.b!=0)
    {
        lazer c(b.b/b.a,-1,tmp1.y-b.b*tmp1.x/b.a);
        tmp3=sym(tmp2,c);
    }
    else 
    {
        if(b.a==0)
        {
            lazer c(1,0,-1*tmp1.x);
            tmp3=sym(tmp2,c);
        }
        else
        {
            lazer c(0,1,-1*tmp1.y);
            tmp3=sym(tmp2,c);
        }
    }
    lazer newlazer(tmp3.y-tmp1.y,-1*(tmp3.x-tmp1.x),((tmp3.x-tmp1.x)*tmp1.y)-(tmp3.y-tmp1.y)*tmp1.x,tmp1.x,tmp1.y);
    newlazer.x1=tmp3.x;
    newlazer.y1=tmp3.y;
    return newlazer;
}

7.愉快地记录答案，输出，提交，然后ac

然后这是完整代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
double Pi=3.141592653589793238462;
int n,m;
int w,E;
double x,y;
int cnt;
double ans;
int res=-1;
bool shoot[10010];
struct Point
{
    double x,y;
    Point(double x = 0, double y = 0) : x(x),y(y) {};
    void read()
    {
        scanf("%lf %lf",&x,&y);
    }
    Point operator - (const Point &a) const
    {
        return Point(a.x - x, a.y - y);
    }
}a[1010][10],g[1010],yuanxin[1010];

struct lazer
{
    double x,y;
    double a,b,c;
    double x1,y1;
    lazer(double a=0, double b=0,double c=0,double x=0,double y=0) : a(a),b(b),c(c),x(x),y(y) {};
};
lazer lastlazer;
lazer xianduan[10010];
double r[1010];

Point xianduana[10100],xianduanb[10100];

Point inter(lazer a,lazer b)
{
    double y=((a.a*b.c-b.a*a.c)/(b.a*a.b-a.a*b.b));
    double x;
    if(a.a!=0)x=(-1*a.b*y-a.c)/a.a;
    else x=(-1*b.b*y-b.c)/b.a;
    Point intersp(x,y);
    return intersp;
}

Point sym(Point a,lazer b)
{
    if(b.a==0)
    {
        Point tmp(a.x,(-1*b.c/b.b)-(a.y-(-1*b.c/b.b)));
        return tmp;
    }
    if(b.b==0)
    {
        Point tmp((-1*b.c/b.a)-(a.x-(-1*b.c/b.a)),a.y);
        return tmp;
    }
    lazer nl(b.b,-1*b.a,b.a*a.y-b.b*a.x);
    Point tmpp=inter(nl,b);
    double tmpx=2*tmpp.x-a.x;
    double tmpy=2*tmpp.y-a.y;
//	cout<<tmpx<<" "<<tmpy<<endl;
    Point tmp(tmpx,tmpy);
    return tmp;
}

lazer bounce(lazer a,lazer b)
{
    Point tmp1=inter(a,b);
//	cout<<tmp1.x<<" "<<tmp1.y<<endl;
    if((-1*a.a/a.b)*(-1*b.a/b.b)==-1)
    {
        lazer nl(a.a,a.b,a.c,tmp1.x,tmp1.y);
        return nl;
    }
    Point tmp2;
    tmp2.x=a.x,tmp2.y=a.y;
    Point tmp3;
    if(b.a!=0&&b.b!=0)
    {
        lazer c(b.b/b.a,-1,tmp1.y-b.b*tmp1.x/b.a);
        tmp3=sym(tmp2,c);
    }
    else 
    {
        if(b.a==0)
        {
            lazer c(1,0,-1*tmp1.x);
            tmp3=sym(tmp2,c);
        }
        else
        {
            lazer c(0,1,-1*tmp1.y);
            tmp3=sym(tmp2,c);
        }
    }
    //if(a.a!=0)tmp2.x=(-1*a.b*(tmp1.y-1)-a.c)/a.a,tmp2.y=tmp1.y-1;
    //else tmp2.y=-1*a.c/a.b,tmp2.x=tmp1.x-1;

//		cout<<tmp3.x<<" "<<tmp3.y<<endl;
    lazer newlazer(tmp3.y-tmp1.y,-1*(tmp3.x-tmp1.x),((tmp3.x-tmp1.x)*tmp1.y)-(tmp3.y-tmp1.y)*tmp1.x,tmp1.x,tmp1.y);
    newlazer.x1=tmp3.x;
    newlazer.y1=tmp3.y;
    return newlazer;
}

double cross(Point A, Point B)
{
    return A.x * B.y - A.y * B.x;
}

double area(Point a, Point b, Point c)
{
    Point A,B;
    A=b-a;
    B=c-a;
    return cross(A,B);
}

double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
}

bool updown(lazer a,Point b)
{
    if((-1*a.c-a.a*b.x)/a.b>b.y)return 1;
    if((-1*a.c-a.a*b.x)/a.b<b.y)return 0;
    return 2;
}

bool isinter(lazer a,lazer xd)
{
    Point tmp1(xd.x,xd.y);
    Point tmp2(xd.x1,xd.y1);
    if((updown(a,tmp1)^updown(a,tmp2))!=1)return 0;
    Point tmp3=inter(a,xd);
    if((a.x>=tmp3.x&&a.x<=a.x1)||(a.x<=tmp3.x&&a.x>=a.x1))return 0;
    //cout<<" "<<tmp3.x<<" "<<a.x<<" "<<a.x1<<endl;
    return 1;
}

int main()
{
    /*double xx1,yy1,xx2,yy2;
    double a1,b1,c1;
    cin>>a1>>b1>>c1;
    cin>>xx1>>yy1>>xx2>>yy2;	
    lazer xx(a1,b1,c1,xx1,yy1);
    xx.x1=xx2;
    xx.y1=yy2;
    cin>>a1>>b1>>c1;
    cin>>xx1>>yy1>>xx2>>yy2;
    lazer yy(a1,b1,c1,xx1,yy1);
    yy.x1=xx2;
    yy.y1=yy2;
    cout<<isinter(xx,yy);*/
    scanf("%d",&n);
    for(int _=1;_<=n;_++)
    {
        scanf("%d",&m);
        if(m==0)
        {
        	yuanxin[_].read();
        	scanf("%lf",&r[_]);
        }
        Point p0,p1,p2;
        double sum_x,sum_y,sum_area;
        p0.read();
        a[_][0].x=m;
        a[_][1]=p0;
        p1.read();
        a[_][2]=p1;
        sum_x=sum_y=sum_area=0.0;
        for(int i=2;i<m;i++)
        {
            p2.read();
            a[_][i+1]=p2;
            double tp=area(p0,p1,p2);
            sum_x+=(p0.x+p1.x+p2.x)*tp;
            sum_y+=(p0.y+p1.y+p2.y)*tp;
            sum_area+=tp;
            p1=p2;
        }
        Point G(sum_x/sum_area/3.0,sum_y/sum_area/3.0);
        g[_]=G;
    }
    for(int _=1;_<=n;_++)
    {
    	int k;
    	scanf("%d",&k);
    	if(r[_]!=0)continue;
        for(int j=1;j<=a[_][0].x;j++) 	
    	{
    		for(int i=1;i<=k;i++)
    		{
    			double delx=a[_][j].x-g[_].x;
            	double dely=a[_][j].y-g[_].y;
            	a[_][j].x=g[_].x+dely;
            	a[_][j].y=g[_].y-delx;
            }
            //cout<<a[_][j].x<<" "<<a[_][j].y<<endl;
            if(j==a[_][0].x)
            {
                xianduan[++cnt].x=a[_][j].x;
                xianduan[cnt].y=a[_][j].y;
                xianduan[cnt].x1=a[_][1].x;
                xianduan[cnt].y1=a[_][1].y;				
                xianduan[cnt].a=a[_][j].y-a[_][1].y;
                xianduan[cnt].b=-1*(a[_][j].x-a[_][1].x);
                xianduan[cnt].c=((a[_][j].x-a[_][1].x)*a[_][1].y)-(a[_][j].y-a[_][1].y)*a[_][1].x;			
            }
            else
            {
                xianduan[++cnt].x=a[_][j].x;
                xianduan[cnt].y=a[_][j].y;
                xianduan[cnt].x1=a[_][j+1].x;
                xianduan[cnt].y1=a[_][j+1].y;	
                xianduan[cnt].a=a[_][j].y-a[_][j+1].y;
                xianduan[cnt].b=-1*(a[_][j].x-a[_][j+1].x);
                xianduan[cnt].c=((a[_][j].x-a[_][j+1].x)*a[_][j+1].y)-(a[_][j].y-a[_][j+1].y)*a[_][j+1].x;	
            }
                //xianduan[j]
        }
    }
    scanf("%d%d",&w,&E);
    scanf("%lf%lf",&x,&y);
    for(double i=0;i<=360.0;i+=0.01)
    {
    	memset(shoot,0,sizeof(shoot));
        lazer st;
        st.x=x;
        st.y=y;
        double u=i;
        if(u>180)u-=180;
        if(u!=90&&u!=270)
        st.a=tan((u)*Pi/180),st.b=-1,st.c=(y-x*tan((u)*Pi/180));
        else
        {
            st.a=1;
            st.b=0;
            st.c=-1*x;
        }
        if(i==90||i==270)
        {
            if(i==90)st.x1=x,st.y1=y+10;
            else st.x1=x,st.y1=y-10;
        }
        else
        {
            if((i>=0&&i<=90)||(i>=270&&i<=360))
            st.x1=x+10,
            st.y1=(-st.c-st.a*st.x1)/(st.b);
            else
            st.x1=x-10,
            st.y1=(-st.c-st.a*st.x1)/(st.b);
        }
        bool flag=0;
        int cntt=0;
        do
        {
            flag=0;
            double minx=100000000;
            int hehe=1;
            for(int j=1;j<=cnt;j++)
            {
                if(!shoot[j]&&isinter(st,xianduan[j]))
                {
                    flag=1;
                    Point tmmp=inter(st,xianduan[j]);
                    if(minx>dist(tmmp.x,tmmp.y,st.x,st.y))
                    {
                        minx=dist(tmmp.x,tmmp.y,st.x,st.y);
                        hehe=j;
                    }
                }				
            }	
            if(flag==0)break;
            shoot[hehe]=1;
            cntt++;
            st=bounce(st,xianduan[hehe]);
            //cout<<hehe<<" "<<endl;
            //cout<<st.a<<" "<<st.b<<" "<<st.c<<endl; 
            //cout<<st.x<<" "<<st.y<<" "<<st.x1<<" "<<st.y1<<endl;
        }
        while(1);
        if(abs(w*cntt-E)<res||res==-1)
        {
        	res=abs(w*cntt-E);
        	ans=i;
    	}
        //if(cntt!=0)cout<<i<<" "<<cntt<<endl,getchar();
    }
    printf("%.2lf\n",ans);
    return 0;
}
/*
2
4
0 0
0 4
4 4
4 0
3
8 0
12 4
12 0
0 0
1 2
5 5
*/

如果你有任何问题，请加入我的团队发帖提问或者加我的qq，私信我可能看不见

ID

3221

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

萃香的新年宴会第二题题解#2封兽鵺的激光游戏

by Wy12121212

我先说一下吧，这道题确实挺神仙的，如果你实在不想写copy我的代码我也不反对，当然如果你执意要写我也很赞成qwq

封兽鵺的激光游戏

信息

1 条题解

自动搬运

以下是正文

萃香的新年宴会第二题题解#2封兽鵺的激光游戏

by Wy12121212

我先说一下吧，这道题确实挺神仙的，如果你实在不想写copy我的代码我也不反对，当然如果你执意要写我也很赞成qwq

封兽鵺的激光游戏

信息

还没有账户？

登录