zoj1158判断2线段完全相交

一个正方形的古老墓园，有n面墙，墙的端点都在正方形的边上。已知墓碑的地点(x,y)，问从外面一直到达墓碑至少要凿开几个门，而且规定门只能凿在当前点段的中点。 思路很巧妙，因为从一个点到终点不可能“绕过”围墙，只能传过去，所以门是否开在中点是无所谓

一个正方形的古老墓园，有n面墙，墙的端点都在正方形的边上。已知墓碑的地点(x,y)，问从外面一直到达墓碑至少要凿开几个门，而且规定门只能凿在当前点段的中点。

思路很巧妙，因为从一个点到终点不可能“绕过”围墙，只能传过去，所以门是否开在中点是无所谓的，只要求四周线段中点到终点的线段与墙的最少交点个数即可。更进一步，实际上，只需判断四周围墙的所有点与终点的连线与内墙的最少交点加一即可。

const double eps = 1e-8 ;

double  add(double x , double y){
        if(fabs(x+y)   lisline  ;
vector lispoint  ;

int  main(){
     int t  , k  , n , i  , j  , T = 1 ;
     Point  ed  , ls , ld ;
     cin>>t ;
     while(t--){
          cin>>n ;
          lispoint.clear() ;
          lisline.clear() ;
          lispoint.push_back(Point(0.0 , 0.0)) ;
          lispoint.push_back(Point(0.0 , 100.0)) ;
          lispoint.push_back(Point(100.0 , 0.0)) ;
          lispoint.push_back(Point(100.0 , 100.0)) ;
          for(i = 1 ; i  

查看更多关于zoj1158判断2线段完全相交的详细内容...