我剛開(kāi)始被這道題目的名字吸引了，因?yàn)樗蛯毑赜嘘P(guān)，呵呵^_^不過(guò)把題目讀完以后才發(fā)現(xiàn)這道題是個(gè)無(wú)聊的計(jì)算幾何題 ，說(shuō)實(shí)話(huà)有點(diǎn)失望。。。
題目的大意是這樣的：尋寶者在一個(gè)被分割成很多房間的正方形迷宮里尋寶，這個(gè)迷宮是100*100的正方形而且四個(gè)頂點(diǎn)坐標(biāo)一定。尋寶者具有把墻鑿穿通過(guò)的能力，若尋寶者可以從正方形的任意一個(gè)邊界進(jìn)入，問(wèn)到達(dá)藏寶地點(diǎn)最少要穿過(guò)幾道墻？
這個(gè)題的解法是：枚舉每一個(gè)入口。然后在所有的情況中取穿墻數(shù)最少的輸出即可。
考察每一個(gè)入口的時(shí)候，枚舉每條邊，如果起點(diǎn)和終點(diǎn)在這條直線(xiàn)的兩側(cè)，那么尋寶者一定要穿過(guò)一道墻。于是此題轉(zhuǎn)化成了判斷2點(diǎn)是否在一條直線(xiàn)的異側(cè)的問(wèn)題。模板解決~
由于自己寫(xiě)的有點(diǎn)冗長(zhǎng)，于是參考了下網(wǎng)上的代碼，發(fā)現(xiàn)將所有邊界上的點(diǎn)按照角度排序的確是個(gè)很巧妙的方法，學(xué)習(xí)了^_^
//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// 定義一條線(xiàn)段，用起點(diǎn)和終點(diǎn)來(lái)表示
{
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;
}