我剛開始被這道題目的名字吸引了，因為它和寶藏有關，呵呵^_^不過把題目讀完以后才發現這道題是個無聊的計算幾何題 ，說實話有點失望。。。
題目的大意是這樣的：尋寶者在一個被分割成很多房間的正方形迷宮里尋寶，這個迷宮是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(0, 0);
mypoint[countnum++] = Point(100, 0);
mypoint[countnum++] = Point(0, 100);
mypoint[countnum++] = Point(100, 100);
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;
}