The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1066——Treasure Hunt解题报告

我刚开始被这道题目的名字吸引了,因为它和宝藏有关,呵呵^_^不过把题目读完以后才发现这道题是个无聊的计算几何题 ,说实话有点失望。。。

题目的大意是这样的:寻宝者在一个被分割成很多房间的正方形迷宫里寻宝,这个迷宫是100*100的正方形而且四个顶点坐标一定。寻宝者具有把墙凿穿通过的能力,若寻宝者可以从正方形的任意一个边界进入,问到达藏宝地点最少要穿过几道墙?

这个题的解法是:枚举每一个入口。然后在所有的情况中取穿墙数最少的输出即可。
考察每一个入口的时候,枚举每条边,如果起点和终点在这条直线的两侧,那么寻宝者一定要穿过一道墙。于是此题转化成了判断2点是否在一条直线的异侧的问题。模板解决~

由于自己写的有点冗长,于是参考了下网上的代码,发现将所有边界上的点按照角度排序的确是个很巧妙的方法,学习了^_^

//coded by abilitytao
//Time:2009年8月5日17:50:19

#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
double const EPS = 1e-8;
const int INF = 0xf777777;
#define zero(x) (((x)>0?(x):-(x))<eps) 



struct Point
{
    
double x,y;
    Point()
{}
       Point(
double a, double b):x(a), y(b){}
       
bool operator<(Point a){return atan2(y - 50, x - 50< atan2(a.y - 50, a.x - 50); }
}


struct Line// 定义一条线段,用起点和终点来表示 
{               
    Point a, b; 
    Line() 
{} 
    Line(Point p10, Point p20): a(p10), b(p20) 
{} //Line a(p1,p2);
}



Point mypoint[
64], s, t;
Line myline[
30];
int n, countnum, minnum;

double xmult(Point p1, Point p2 , Point p0)
{
    
return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}

int same_side(Point p1,Point p2,Line l)

    
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>EPS; 
}


int main()
{
    
int i, j, ans;
    minnum 
= INF; countnum = 0;
    mypoint[countnum
++= Point(00);
    mypoint[countnum
++= Point(1000);
    mypoint[countnum
++= Point(0100);
    mypoint[countnum
++= Point(100100);
    
    cin 
>> n;
    
for(i = 0; i < n; i++)
    
{
        scanf(
"%lf%lf%lf%lf",&myline[i].a.x ,&myline[i].a.y ,&myline[i].b.x ,&myline[i].b.y);
        mypoint[countnum
++= myline[i].a;
        mypoint[countnum
++= myline[i].b;
    }

    scanf(
"%lf%lf",&s.x,&s.y);
    
       sort(mypoint, mypoint
+countnum);
       
       
for(i=0;i<countnum;i++ )
       
{
           ans 
= 0;
           t 
= Point( (mypoint[i].x + mypoint[(i+1)%countnum].x)/2, (mypoint[i].y + mypoint[(i+1)%countnum].y)/2 );
           
for(j = 0; j < n; j++)          
               
if(!same_side(s, t, myline[j]))
                   ans
++;
            
if(ans <minnum) minnum = ans;
       }

       
       printf(
"Number of doors = %d\n", minnum+1);
       
return 0;
}

posted on 2009-08-05 23:58 abilitytao 阅读(1471) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理