题解 P4468 【[SCOI2007]折纸】

Hiraeth · 2018-09-16 14:32:36 · 题解

我是真的菜啊

真的好难啊

想了好久好久

大体思路就是：

因为对折次数是有上限的，所以这个值也不会太大，

那么最后提供答案的数据点的结果应该也不会太大，

如果不放心的话，可以开一个unsigned long long

所以就对输入的每个点，把一张折叠了的纸再沿着折痕返回过去，

相当于在一个平面直角坐标系中寻找一个已知点的对称点

数学的手动滑稽

边读边扫，在输入过程中排除中途不符合情况的点，

最后看在初始的图形上有多少的点剩下来，既符合情况的点

要求点关于直线的对称点。

对称点的一种求法是斜率之积为-1

然后求解

这是我打的智障做法……

据大佬讲解可以用旋转向量公式

x1=x0cosB-y0sinB

y1=x0sinB+y0cosB

Orz一波大佬

美丽的折纸 溜了溜了

#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 ;
}