LOJ#2039. 「SHOI2015」激光发生器（计算几何）

逃离我推掉我的手 2022-01-12 09:41 204阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

如果我初中科学老师知道我有一天计算的时候入射角不等于反射角不知道会不会把我抓起来打一顿……

这题本质上就是个模拟，需要的芝士也就计蒜几盒的那点，不过注意细节很多，放到考场上只能看看绝对调不出来的那种

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define inline __inline__ __attribute__((always_inline))
    #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
    #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
    using namespace std;
    int read(){
        R int res,f=1;R char ch;
        while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    const int N=105;const double eps=1e-6,Pi=acos(-1.0),Loli=Pi*0.5;
    inline double abs(R double x){return x<-eps?-x:x;}
    inline int sgn(R double x){return x<-eps?-1:x>eps;}
    struct node{
        double x,y;
        inline node(){}
        inline node(R double xx,R double yy):x(xx),y(yy){}
        inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
        inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
        inline double operator *(const node &b)const{return x*b.y-y*b.x;}
        inline double operator ^(const node &b)const{return x*b.x+y*b.y;}
        inline node operator *(const double &b)const{return node(x*b,y*b);}
        inline double norm(){return sqrt(x*x+y*y);}
        friend double ang(node &a,node &b){return acos((a^b)/a.norm()/b.norm());}//两个向量之间的夹角 
        inline node rot(const double &b){
            //逆时针旋转b度 
            double s=sin(b),c=cos(b);
            return node(x*c-y*s,x*s+y*c);
        }
    }p,v,c;
    struct Line{
        node p,v;
        inline Line(){}
        inline Line(R node a,R node b){p=a,v=b-a;}
        friend node cross(const Line &a,const Line &b){return a.p+a.v*(b.v*(b.p-a.p)/(b.v*a.v));}//两直线交点 
        inline bool on(const node &b){return !sgn((b-p)*v)&&sgn((b-p)^(b-(p+v)))<0;}//判断点是否在线段上 
    }L[N];
    int n,bt;double alf[N],x,y,xx,yy,a,b,bet;
    int main(){
    //  freopen("testdata.in","r",stdin);
        p.x=read(),p.y=read(),v.x=read(),v.y=read(),n=read();
        fp(i,1,n){
            x=read(),y=read(),xx=read(),yy=read(),a=read(),b=read();
            L[i]=Line(node(x,y),node(xx,yy)),alf[i]=a/b;
        }
        bool flag=0;
        fp(T,1,10){
            double mn=1e18;int id=0;
            fp(i,1,n)if(sgn(v*L[i].v)){
                c=cross(Line(p,p+v),L[i]);
                if(L[i].on(c)&&sgn(v^(c-p))>0&&cmin(mn,(c-p).norm()))id=i;
            }
            if(!id)break;
            p=cross(Line(p,p+v),L[id]);
            if(!sgn(v^L[id].v))v=v*-1;
            else{
                c=L[id].v;
                if(sgn(c^v)<0)c=c*-1;
                bet=Loli-ang(v,c),bt=sgn(c*v);
                v=c.rot(bt*(bet*alf[id]-Loli));
            }
            printf("%d ",id),flag=1;
        }
        if(!flag)puts("NONE");
        puts("");
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10696549.html

[Link 1]: https://loj.ac/problem/2039