2016-09-16

POJ 1066 Treasure Hunt【线段交】

题目链接：

题意：

$100 \times 100$的正方形围墙内有$n(n \le 30)$端点在围墙边上的墙。给定终点，问从正方形外部走到终点要经过最少多少堵墙，穿过墙时只能走中点？

分析：

$n$只有30，显然枚举入口。仔细分析我们可以发现只能走墙中点这个信息并没有什么用，因为只要是经过这堵墙，必然要穿过去，实际走的即是直线。
那么我们在枚举入口的时候只需枚举端点，然后求连接起点与终点的线段与其他所有线段的交点个数最小值即可~
顺便复习一下线段交 http://blog.csdn.net/yukizzz/article/details/50816072

代码：

/*************************************************************************
    > File Name: 1066.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/16 11:03:53
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 30 + 5;
double eps = 1e-8;
double add(double a, double b)
{
    if(abs(a + b) < eps * (abs(a) + abs(b)))  return 0;
    else return a + b;
}
struct P{
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y){}
    P operator + (P p){
        return P(add(x, p.x), add(y, p.y));
    }
    P operator -(P p){
        return P(add(x, -p.x), add(y, -p.y));
    }
    double dot(P p){
        return add(x * p.x, y *p.y);
    }
    double det(P p){
        return add(x * p.y, - y * p.x);
    }
    P operator *(double d){
        return P(x * d, y * d);
    }
}p[maxn << 1];
P des;
bool onseg(P p1, P p2, P q)
{
    return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
}
P intersection(P p1, P p2, P q1, P q2)
{
    return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}
int main (void)
{
	int n;scanf("%d", &n);
	for(int i = 0; i < 2 * n; i++){
		scanf("%lf%lf", &p[i].x, &p[i].y);
	}
	int ans, res = n + 1;
	double x, y;scanf("%lf%lf", &des.x, &des.y);
	for(int i = 0; i < 2 * n; ++i){
		ans = 1;
		for(int j = 0; j < 2 * n; j += 2){
			if(j == i || j == i - 1) continue;
			P tmp = intersection(p[i], des, p[j], p[j + 1]);
			ans += onseg(p[j], p[j + 1], tmp) && onseg(p[i], des, tmp); 
		}
		res = min(res, ans);
	}
	printf("Number of doors = %d\n", res);
	return 0;
}