1 条题解

  • 1
    @ 2022-9-5 22:39:58
    #include<bits/stdc++.h>
    
    using namespace std ; 
    
    const int MAXN = 10 ; 
    const int MAXM = 60 ; 
    const double eps = 1e-6 ; 
    int N , M ;
    
    struct Point {
        double x , y ; 
        Point ( const double x , const double y ) :
        x ( x ) , y ( y ) {} ;
    } ; 
    
    struct Vector {
        double x , y ; 
        Vector ( const double x , const double y ) : 
        x ( x ) , y ( y ) {} ; 
    } ; 
    
    struct Line {
        Point From , To ; 
        Line ( const double x1 , const double y1 , 
               const double x2 , const double y2 ) :
        From ( x1 , y1 ) , To ( x2 , y2 ) {} ;
        Vector toVector () const ;
    } ;
    
    Vector operator - ( const Point & First , const Point & Second ) {
        return Vector ( First . x - Second . x , First . y - Second . y ) ; 
    } 
    
    Point operator - ( const Point & First , const Vector & Second ) {
        return Point ( First . x - Second . x , First . y - Second . y ) ; 
    } 
    
    Vector operator * ( const double k , const Vector & Input ) {
        return Vector ( k * Input . x , k * Input . y ) ; 
    }
    
    Point operator + ( const Point & First , const Vector & Second ) {
        return Point ( First . x + Second . x , First . y + Second . y ) ; 
    }
    
    
    double operator ^ ( const Vector & First , const Vector & Second ) {
        return First . x * Second . y - First . y * Second . x ; 
    }  
    
    double operator * ( const Vector & First , const Vector & Second ) {
        return First . x * Second . x + First . y * Second . y ; 
    }
    
    double abs ( const Vector & Input ) {
        return sqrt ( Input . x * Input . x + Input . y * Input . y ) ; 
    }
    
    Vector Line :: toVector () const { return To - From ; }  
    
    vector < Line > Opts ; 
    
    Point reflect ( const Point o , const Line L ) {
        const double dis = ( ( L . From - o ) ^ ( L . To - o ) ) / abs ( L . toVector () ) ; 
        const Vector Lp = 1.0 / abs ( L . toVector () ) * L . toVector () ; 
        return o + 2.0 * dis * Vector ( Lp . y , - Lp . x ) ;
    }
    
    int Query ( const Point o , const int T ) {
        if ( T == -1 ) 
            return ( eps <= o . x && o . x <= 100.0 - eps ) && 
                   ( eps <= o . y && o . y <= 100.0 - eps ) ; 
        const double CrossValue =   ( ( Opts [ T ] . From - o ) ^ ( Opts [ T ] . To - o ) ) ;
        if ( CrossValue < - eps ) return 0 ;     
        if ( - eps <= CrossValue && CrossValue <= eps ) return 0 ; 
        return Query ( o , T - 1 ) + 
               Query ( reflect ( o , Opts [ T ] ) , T - 1 ) ; 
    }
    
    int main () {
        scanf ( "%d" , & N ) ; 
        for ( int i = 0 ; i < N ; ++ i ) {
            double x1 , y1 , x2 , y2 ; 
            scanf ( "%lf%lf%lf%lf" , & x1 , & y1 , & x2 , & y2 ) ; 
            Opts . push_back ( Line ( x1 , y1 , x2 , y2 ) ) ; 
        } 
        scanf ( "%d" , & M ) ; 
        while ( M -- ) {
            double x , y ; 
            scanf ( "%lf%lf" , & x , & y ) ; 
            printf ( "%d\n" , Query ( Point ( x , y ) , N - 1 ) ) ;
        }
        return 0 ;
    }
    
    • 1

    信息

    ID
    3399
    时间
    2000ms
    内存
    125MiB
    难度
    7
    标签
    递交数
    3
    已通过
    3
    上传者