题意：
平面上有n条线段，一次给出这n条线段的两个端点的坐标。问怪兽能否从坐标原点逃到无穷远处。(两直线最多有一个交点，且没有三线共交点的情况)
分析：
首先说明一下线段的规范相交：就是交点唯一而且在两条线段的内部。
如果输入中有一条线段uv没有和其他任何一条线段规范相交，那么怪兽一定是可以从u走到v的。
所以我们可以建一个图模型，如果u可以走到v则添加一条边，最后BFS一下看能否从起点走到终点。
再考虑下特殊情况：
题中虽然说三线不会共交点，但貌似不包括三线共端点的情况。
比如这种情况：
线段AB和BC均不和其他线段规范相交，所以会认为A能走到B，B能走到C。但事实上，这个三角形是封闭的，内部和外部不是连通的。
解决办法就是将线段适当加宽一下(代码中使线段想两侧延伸了1e-6)，使其变为规范相交。
还有一种情况就是：
当两个共端点的线段共线的时候，也会出现问题。比如本来应该是封闭的，但因为是根据线段的规范相交来判断是否前进的，所以可能使其变成一条通路。
解决办法就是加宽后端点位于其他线段上的点不参与构图。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std; const double eps = 1e-;
int dcmp(double x)
{
if(fabs(x) < eps) return ;
else return x < ? - : ;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y) {}
};
typedef Point Vector; Point operator + (const Point& a, const Point& b) { return Point(a.x+b.x, a.y+b.y); }
Point operator - (const Point& a, const Point& b) { return Point(a.x-b.x, a.y-b.y); }
Vector operator * (const Vector& a, double p) { return Vector(a.x*p, a.y*p); }
Vector operator / (const Vector& a, double p) { return Vector(a.x/p, a.y/p); }
bool operator < (const Point& a, const Point& b)
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool operator == (const Point& a, const Point& b)
{
return a.x == b.x && a.y == b.y;
}
double Dot(const Vector& a, const Vector& b) { return a.x*b.x + a.y*b.y; }
double Cross(const Vector& a, const Vector& b) { return a.x*b.y - a.y*b.x; }
double Length(const Vector& a) { return sqrt(Dot(a, a)); }
bool SegmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2)
{
double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
return dcmp(c1)*dcmp(c2) < && dcmp(c3)*dcmp(c4) < ;
} bool OnSegment(const Point& p, const Point& a, const Point& b)
{
return dcmp(Cross(a-p, b-p)) == && dcmp(Dot(a-p, b-p)) < ;
} const int maxn = + ;
int n, V;
int G[maxn][maxn], vis[maxn];
Point p1[maxn], p2[maxn]; bool OnAnySegment(const Point& p)
{
for(int i = ; i < n; ++i)
if(OnSegment(p, p1[i], p2[i])) return true;
return false;
} bool IntersectionWithAnySegment(const Point& a, const Point& b)
{
for(int i = ; i < n; ++i)
if(SegmentProperIntersection(a, b, p1[i], p2[i])) return true;
return false;
} bool dfs(int u)
{
if(u == ) return true;
vis[u] = ;
for(int v = ; v < V; ++v)
if(G[u][v] && !vis[v] && dfs(v)) return true;
return false;
} bool find_path()
{
vector<Point> vertices;
vertices.push_back(Point(0.0, 0.0));
vertices.push_back(Point(1e5, 1e5));
for(int i = ; i < n; ++i)
{
if(!OnAnySegment(p1[i])) vertices.push_back(p1[i]);
if(!OnAnySegment(p2[i])) vertices.push_back(p2[i]);
}
V = vertices.size();
memset(G, , sizeof(G));
memset(vis, , sizeof(vis));
for(int i = ; i < V; ++i)
for(int j = i+; j < V; ++j)
if(!IntersectionWithAnySegment(vertices[i], vertices[j]))
G[i][j] = G[j][i] = ;
return dfs();
} int main(void)
{
#ifdef LOCAL
freopen("2797in.txt", "r", stdin);
#endif while(scanf("%d", &n) == && n)
{
double x1, y1, x2, y2;
for(int i = ; i < n; ++i)
{
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
Point a = Point(x1, y1);
Point b = Point(x2, y2);
double l = Length(a-b);
Vector v0 = (a-b) / l * 1e-;
p1[i] = a + v0;
p2[i] = b - v0;
}
if(find_path()) puts("no");
else puts("yes");
} return ;
}
代码君
