nyoj-83 迷宮尋寶（二） （計算幾何）

迷宮尋寶（二）

描述

一個叫ACM的尋寶者找到了一個藏寶圖，它根據藏寶圖找到了一個迷宮，這是一個很特別的迷宮，迷宮是一100*100的個正方形區域，裡面有很多牆，這些牆都是由一些直線構成的，如下圖。

牆把迷宮分隔成很多藏寶室，任何兩個藏寶室之間都沒有門。

ACM現在准備用開鑿設備在相鄰兩個藏寶室的牆中間鑿開一個門，最終取出迷宮中的寶物。

但是，開鑿門是一件很費力費時的工作，ACM想開鑿盡量少的門取出寶物，現在請你寫一個程序來幫助它判斷一下最少需要開幾個門吧。

輸入

第一行輸入一個正數N(N<10)表示測試數據組數
每組測試數據的第一行是一個整數n(0<=n<=30),代表了牆的個數，隨後的n行裡每行有四個整數x1,x2,y1,y2，這四個數分別是代表一個牆的兩個端點的坐標。外圍的正方形四個頂點固定在(0,0)(0,100)(100,0)(100,100)這四堵個牆不在上面的n個數裡。注意，不能在兩個線的交點處開鑿門。
數據保證任意兩個中間牆的交點不在四周的牆上。
輸完所有的牆後，輸入兩個數，x,y（可能不是整數），表示寶藏的坐標。

輸出

輸出最少需要開鑿的門的個數

樣例輸入

1
7 
20 0 37 100 
40 0 76 100 
85 0 0 75 
100 90 0 90 
0 71 100 61 
0 14 100 38 
100 47 47 100 
54.5 55.4 

樣例輸出

2

思路：

計算幾何問題；

本題思路是枚舉地圖四周邊界的所有點，使每一個邊界點和終點構成一個線段，求出所有線段和牆相交的最少次數就是結果最後的結果；

要注意的是枚舉的雖然是整數點，但實際是可取整數之間的點的；所以，題目中雖然明確不能在兩牆交點處開鑿，在這兒是不需要考慮的，因外相交了只要有一點偏差，取得的ct值仍是不變的；

代碼：

#include 
#include 
#define INF 0x7fffffff
#define N 40

struct Point{
	double x;
	double y;
};

struct Line{
	Point p1;
	Point p2;
};

int num;
double jx = 1e-6;
Line l[N];

double det(double x1, double y1, double x2, double y2)			// 計算叉積 
{
	return x1 * y2 - x2 * y1;
}

double get_dir(Point a, Point b, Point c)			// 計算向量ab在向量ac的哪個方向(正數為逆時針,負數為順時針， 零為同向或者反向)
{
	return det((b.x - a.x), (b.y - a.y), (c.x - a.x), (c.y - a.y));
}

bool Cross(Line* a, Line* b)						// 判斷兩線段關系
{
	double q1 = get_dir(a ->p1, a ->p2, b ->p1);
	double q2 = get_dir(a ->p1, a ->p2, b ->p2);
	double q3 = get_dir(b ->p1, b ->p2, a ->p1);
	double q4 = get_dir(b ->p1, b ->p2, a ->p2);
	if(q1 * q2 < 0 && q3 * q4 < 0)					// 判斷兩線段是否完全相交
		return 1;
	else
		return 0;
}

int GetCross(Line* a, int x, int y)
{
	int ct = 0;
	a ->p2.x = x;
	a ->p2.y = y;
	for(int k = 0; k < num; k ++){				// 枚舉所有線段（牆）
		if(Cross(a, &l[k]))						// 判斷兩線是否相交
			ct ++;
	}

	return ct;
}

int main()
{
	Line a;
	int loop, i;
	scanf("%d", &loop);
	while(loop --){
		scanf("%d", &num);
		for(i = 0; i < num; i ++)
			scanf("%lf%lf%lf%lf", &l[i].p1.x, &l[i].p1.y, &l[i].p2.x, &l[i].p2.y);
		scanf("%lf%lf", &a.p1.x, &a.p1.y);

		int ans = INF, ct;
		for(i = 1; i < 100; i ++){					// 枚舉所有的起點，與終點（寶藏坐標）構成一條線段
			ct = GetCross(&a, 0, i);
			if(ans > ct)							// 記錄最少交點數
				ans = ct;

			ct = GetCross(&a, 100, i);
			if(ans > ct)
				ans = ct;

			ct = GetCross(&a, i, 0);
			if(ans > ct)
				ans = ct;

			ct = GetCross(&a, i, 100);
			if(ans > ct)
				ans = ct;
		}
		printf("%d\n", ans + 1);
	}

	return 0;
}