poj1066巧妙的线段相交的应用

初看到这道题一般人的第一个想法基本上就是建图，找最短路。但一想到这个做法的无论代码长度还是算法复杂度都实在浪费时间之后，就决定还不如不做了，觉得应该有简单的做法。

想了下：从外围四个墙的某一个门进来，走到宝藏，最小走几个门，实际就是进门点和宝藏的连线goalLine穿过几个点。

证明不好证，但如果说明大体的思想其实挺简单的：思想有点像两点之间直线最短。不要去管纵横交错的小线段，只管一开始原始输入的线段，因为在正方形范围内，这些线段可以想象为无限长，进门的点和宝藏点中间横跨着k条直线（墙 ），你就无法绕过它们，只能穿过它们 ，你往左往右走都只会徒增加你要穿过的墙，就这最基本的k道墙你总是要穿过。

就如下简单示意图，可以看到从进门点到宝藏，总有3条线你必须穿过。

所以问题就变成了，外围小线段的中点与宝藏的连线，与内部线的交点个数。

后来我试了下将其变成，外围小线段的端点与宝藏的连线，与内部线的交点个数，也ac了，但是我感觉这大概是数据比较弱的缘故，推了下感觉好像不行。有哪位兄弟真的认真推导过了，欢迎指正。。

下面的是用端点与宝藏的连线的代码（觉得用线段中点的才是保险的 ，人比较懒就算了）。。

#include <iostream>#include <vector>using namespace std;class Point{public:Point(){x=0.0f;y=0.0f;}Point(double tx,double ty){x=tx;y=ty;}double x,y;};class Segment{public:Segment(){}Segment(Point p1,Point p2){point1=p1;point2=p2;}Point point1,point2;};//return (p2-p1)*(p3-p1)double CrossProduct(Point p1,Point p2,Point p3){Point vec1=Point(p2.x-p1.x,p2.y-p1.y);Point vec2=Point(p3.x-p1.x,p3.y-p1.y);return (vec1.x*vec2.y - vec1.y*vec2.x );}bool SegmentInteract(Segment seg1,Segment seg2){double d1=CrossProduct(seg2.point1,seg2.point2,seg1.point1);double d2=CrossProduct(seg2.point1,seg2.point2,seg1.point2);double d3=CrossProduct(seg1.point1,seg1.point2,seg2.point1);double d4=CrossProduct(seg1.point1,seg1.point2,seg2.point2);if(d1*d2<0 && d3*d4<0)return true;return false;}int main(){vector<Segment> segVec;vector<Point> pointVec;int iSegment;cin>>iSegment;double px1,px2,py1,py2;for(int i=0;i<iSegment;i++){Point p1,p2;cin>>p1.x>>p1.y>>p2.x>>p2.y;segVec.push_back(Segment(p1,p2));pointVec.push_back(p1);pointVec.push_back(p2);}pointVec.push_back(Point(0,0));pointVec.push_back(Point(0,100));pointVec.push_back(Point(100,100));pointVec.push_back(Point(100,0));Point goalPoint;cin>>goalPoint.x>>goalPoint.y;int MinDoorNumber=1<<30;for(vector<Point>::iterator pointIter=pointVec.begin();pointIter!=pointVec.end();pointIter++){int iInteractNumber=0;for(vector<Segment>::iterator segIter=segVec.begin();segIter!=segVec.end();segIter++){if(SegmentInteract(Segment(goalPoint,*pointIter),*segIter)){iInteractNumber++;}}if(iInteractNumber<MinDoorNumber){MinDoorNumber=iInteractNumber;}}if(MinDoorNumber==1<<30)MinDoorNumber=0;cout<<"Number of doors = "<<MinDoorNumber+1<<endl;return 0;}