萃香的新年宴会第二题题解#2封兽鵺的激光游戏
Wy12121212 · · 题解
萃香的新年宴会第二题题解#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，私信我可能看不见