POJ 1066 Treasure Hunt (线段与线段相交) -

题目地址：http://poj.org/problem?id=1066

可以1）从相邻两点的中间出发，求中间穿过多少直线

但首先要极角排序，而且极角相同情况下离原点近的在前面

也可以2）直接从每个墙的端点出发，这样就不用再排序了

注意：n=0时要输出1

1）方法代码如下

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double EPS=1e-10;
#define Vector Point
int minW;
struct Point{double x,y;Point(double x=0,double y=0) :x(x),y(y) {}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}
};
Point t;
struct Wall{Point x,y;Wall(Point x,Point y) :x(x),y(y){} 
};
vector<Wall> walls;
vector<Point> points;bool IsZero(double x){  //判断x是否为零 return -EPS<x&&x<EPS;
}
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;
}
int Sign(double x){   if(IsZero(x)) return 0;return x<0.0?-1:1;
}
bool cmp(const Point& p1,const Point& p2){if(IsZero(cross(p1,p2))) return hypot(p1.x,p1.y)<hypot(p2.x,p2.y); //同一极角的，近的在前面 return Sign(cross(p1,p2))>0;
}void solve(Point e)
{int mW=0;for(int i=0;i<walls.size();i++){Point x=walls[i].x,y=walls[i].y;if(Sign(cross(t-e,x-e))*Sign(cross(t-e,y-e)) < 0   //判断符号再乘，不然精度不够会WR && Sign(cross(y-x,t-x))*Sign(cross(y-x,e-x)) < 0 ) mW++;if(mW>minW) return;}minW=min(mW,minW);
}
int main()
{double x1,y1,x2,y2;int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);Point p1(x1,y1),p2(x2,y2);points.push_back(p1);points.push_back(p2); walls.push_back(Wall(p1,p2));}sort(points.begin(),points.end(),cmp);double r,c;scanf("%lf%lf",&r,&c);t=Point(r,c); minW=walls.size();for(int i=0;i<points.size();i++){double x=(points[i].x+points[(i+1)%points.size()].x)/2.0;double y=(points[i].y+points[(i+1)%points.size()].y)/2.0;solve(Point(x,y));}printf("Number of doors = %d\n",minW+1);return 0;
} 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double EPS=1e-10;
#define Vector Point
int minW;
struct Point{double x,y;Point(double x=0,double y=0) :x(x),y(y) {}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}
};
Point t;
struct Wall{Point x,y;Wall(Point x,Point y) :x(x),y(y){} 
};
vector<Wall> walls;
vector<Point> points;bool IsZero(double x){  //判断x是否为零 return -EPS<x&&x<EPS;
}
double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;
}
int Sign(double x){   if(IsZero(x)) return 0;return x<0.0?-1:1;
}
void solve(Point e)
{int mW=0;for(int i=0;i<walls.size();i++){Point x=walls[i].x,y=walls[i].y;if(Sign(cross(t-e,x-e))*Sign(cross(t-e,y-e)) < 0   //判断符号再乘，不然精度不够会WR && Sign(cross(y-x,t-x))*Sign(cross(y-x,e-x)) < 0 ) mW++;if(mW>minW) return;}minW=min(mW,minW);
}
int main()
{double x1,y1,x2,y2;int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);Point p1(x1,y1),p2(x2,y2);points.push_back(p1);points.push_back(p2); walls.push_back(Wall(p1,p2));}double r,c;scanf("%lf%lf",&r,&c);t=Point(r,c); minW=walls.size();for(int i=0;i<points.size();i++){solve(walls[i].x);solve(walls[i].y);}printf("Number of doors = %d\n",minW+1);return 0;
}