POJ-1066

题解告诉我：
大意：在一个矩形区域内，有n条线段，线段的端点是在矩形边上的，有一个特殊点，问从这个点到矩形边的最少经过的线段条数最少的书目，穿越只能在中点穿越
思路：需要巧妙的转换一下这个问题，因为从一个点到终点不可能“绕过”围墙，只能穿过去，所以门是否开在中点是无所谓的，只要求四周线段中点到终点的线段与墙的最少交点个数即可。
更进一步，实际上，只需判断四周围墙的所有点与终点的连线与内墙的最少交点加一即可。
代码:

#include<bits/stdc++.h>
using namespace std;
struct point {
	double x;
	double y;
} p[65],ed;
int n;
inline point getmag(point a,point b) {
	point s;
	s.x=b.x-a.x;
	s.y=b.y-a.y;
	return s;
}
inline double multiX(point a,point b) {
	return a.x*b.y-b.x*a.y;
}
inline int intersect(point a,point b) {
	int ans=0;
	if(a.x==b.x&&a.y==b.y)return 0;
	for(int i=1; i<=n; i++) {
		double d1=multiX(getmag(a,p[i]),getmag(a,b))*multiX(getmag(a,p[i+n]),getmag(a,b));
		double d2=multiX(getmag(p[i],a),getmag(p[i],p[i+n]))*multiX(getmag(p[i],b),getmag(p[i],p[i+n]));
		if(d1<=0&&d2<=0)ans++;
	}
	return ans;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);
	scanf("%lf%lf",&ed.x,&ed.y);
	if(n==0) {
		printf("Number of doors = 1\n");
		return 0;
	}
	int ans=2147483647;
	for(int i=1; i<=2*n; i++)ans=min(ans,intersect(p[i],ed));
	printf("Number of doors = %d\n",ans);
	return 0;
}