解题思路

本题主要是判断给定的线段是否能将位于原点的怪物成功封印，即是否能形成一个没有漏洞的封闭区域。代码通过一系列的几何计算和图论算法来实现这个判断。

代码结构与功能

• 几何结构体与命名空间：
  • 定义了Point结构体表示点，Vector是Point的别名表示向量，还定义了Line表示直线，DirLine表示有向直线，Circle表示圆。
  • Punctual命名空间提供了计算两点间距离的函数。Vectorial命名空间包含了向量运算的函数。ComplexVector命名空间提供了基于复数的向量运算。Linear命名空间包含直线相关的操作函数。Triangular命名空间提供了三角形相关的计算函数。Polygonal命名空间包含多边形相关的操作。Circular命名空间包含圆相关的操作函数。
• 主要函数：
  • check函数：用于检查点t是否在所有线段的同侧，若存在线段使得点t在其两侧，则返回false，表示该点不能作为封闭区域的一部分。
  • init函数：读取输入的线段端点坐标，对线段进行微小扩展，将满足check函数的线段端点加入集合S，并构建图G，其中图G的节点是集合S中的点，边表示两个点之间没有与其他线段相交。
  • bfs函数：使用广度优先搜索算法，从起点s开始搜索图G，标记已访问的节点，最后判断终点e是否被访问到，若未被访问到则返回true，表示s和e不连通，即存在封闭区域。
  • main函数：循环读取输入数据，调用init函数进行初始化，然后调用bfs函数判断是否能封印怪物，并输出结果。

算法实现步骤

1. 输入处理：从标准输入读取线段数量N和每条线段的两个端点坐标，将其存储在L和R数组中。
2. 线段扩展：对每条线段，将其两个端点沿着线段方向分别向外扩展一个微小距离bw，得到新的端点坐标，以避免后续计算中出现精度问题。
3. 构建点集和图：将原点(0, 0)和一个无穷远点(inf, inf)加入点集S，然后遍历所有线段的端点，将满足check函数的端点也加入S。接着构建图G，对于S中的任意两个点，如果它们之间的线段不与其他线段相交，则在图G中添加一条边连接这两个点。
4. 判断连通性：使用广度优先搜索算法在图G中从原点(0, 0)开始搜索，标记已访问的节点。如果无穷远点(inf, inf)没有被访问到，说明原点和无穷远点不连通，即存在封闭区域，能成功封印怪物，输出yes；否则，输出no。

复杂度分析

• 时间复杂度：假设输入的线段数量为n。init函数中，读取线段端点坐标需要$O(n)$的时间，构建图G时，对于每一对点需要检查是否与其他线段相交，时间复杂度为$O(n^3)$。bfs函数的时间复杂度为$O(V + E)$，其中V是图G的节点数，E是边数，最坏情况下V = O(n)，E = O(n^2)，所以bfs函数的时间复杂度为$O(n^2)$。因此，总的时间复杂度为$O(n^3)$。
• 空间复杂度：代码中使用了一些数组和容器来存储数据，如L、R、S、G等，最坏情况下，空间复杂度为$O(n^2)$。

输入输出处理

• 输入：从标准输入读取数据，第一行是线段数量N，接下来N行每行包含四个浮点数，表示一条线段的两个端点的坐标。
• 输出：对于每组输入数据，在一行中输出yes或no，表示是否能成功封印怪物。

以输入数据为例，对于第一组数据，有8条线段，经过init函数的处理后，构建出图G，然后通过bfs函数判断原点和无穷远点不连通，所以输出yes，表示能成功封印怪物；对于第二组数据，同样经过处理后，发现原点和无穷远点连通，所以输出no，表示不能成功封印怪物。

算法分析

代码采用了以下核心策略：

1. 几何模型：定义了点、向量、线段、直线等基本几何元素，并实现了它们之间的各种运算（如点积、叉积、距离计算、交点判断等）。
2. 预处理：将每条线段的两端略微延长，避免端点处的精度问题。
3. 图的构建：将原点和无穷远点作为特殊点，检查所有线段的端点是否可以连接而不穿过其他线段，从而构建一个图。
4. 连通性判断：使用BFS算法检查原点和无穷远点是否连通。如果连通，则说明存在一条路径可以从原点到达无穷远，封印失败；否则成功。

代码实现

import math
from collections import deque

# 定义点类
class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
    
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    
    def cross(self, other):
        return self.x * other.y - self.y * other.x
    
    def dot(self, other):
        return self.x * other.x + self.y * other.y
    
    def length_squared(self):
        return self.x**2 + self.y**2
    
    def length(self):
        return math.sqrt(self.length_squared())
    
    def scale(self, scalar):
        return Point(self.x * scalar, self.y * scalar)
    
    def __eq__(self, other):
        eps = 1e-10
        return abs(self.x - other.x) < eps and abs(self.y - other.y) < eps
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __repr__(self):
        return f"({self.x}, {self.y})"

# 判断线段是否相交
def segments_intersect(a1, a2, b1, b2):
    def ccw(A, B, C):
        return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
    
    ccw1 = ccw(a1, a2, b1)
    ccw2 = ccw(a1, a2, b2)
    ccw3 = ccw(b1, b2, a1)
    ccw4 = ccw(b1, b2, a2)
    
    # 标准情况：两线段互相跨立
    if (ccw1 * ccw2 < 0) and (ccw3 * ccw4 < 0):
        return True
    
    # 特殊情况：共线或端点在另一条线段上
    def on_segment(p, a, b):
        return (min(a.x, b.x) - 1e-10 <= p.x <= max(a.x, b.x) + 1e-10 and
                min(a.y, b.y) - 1e-10 <= p.y <= max(a.y, b.y) + 1e-10)
    
    if ccw1 == 0 and on_segment(b1, a1, a2):
        return True
    if ccw2 == 0 and on_segment(b2, a1, a2):
        return True
    if ccw3 == 0 and on_segment(a1, b1, b2):
        return True
    if ccw4 == 0 and on_segment(a2, b1, b2):
        return True
    
    return False

# 检查点是否在线段上（不包括端点）
def point_on_segment(p, a, b):
    if p == a or p == b:
        return False
    return (p - a).cross(b - a) == 0 and (p - a).dot(p - b) < 0

# 判断从原点到无穷远是否存在一条不穿过任何线段的路径
def can_escape(segments):
    origin = Point(0, 0)
    inf_point = Point(1e10, 1e10)  # 表示无穷远点
    
    # 检查原点是否在任何线段上（题目保证不会）
    for a, b in segments:
        if point_on_segment(origin, a, b):
            return False
    
    # 构建图的节点集合：原点、无穷远点和所有线段的端点
    nodes = [origin, inf_point]
    for a, b in segments:
        nodes.append(a)
        nodes.append(b)
    
    # 构建图的邻接表
    adj = {node: [] for node in nodes}
    
    # 检查每对节点之间的线段是否与任何其他线段相交
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            a = nodes[i]
            b = nodes[j]
            intersects = False
            
            # 检查线段a-b是否与任何其他线段相交
            for seg in segments:
                c, d = seg
                # 排除共享端点的情况
                if (a == c or a == d) and (b == c or b == d):
                    continue
                if segments_intersect(a, b, c, d):
                    intersects = True
                    break
            
            if not intersects:
                adj[a].append(b)
                adj[b].append(a)
    
    # BFS检查原点和无穷远点是否连通
    visited = set()
    queue = deque([origin])
    visited.add(origin)
    
    while queue:
        current = queue.popleft()
        if current == inf_point:
            return True  # 存在路径，封印失败
        
        for neighbor in adj[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return False  # 不存在路径，封印成功

# 主函数
def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    
    while True:
        n = int(input[ptr])
        ptr += 1
        if n == 0:
            break
        
        segments = []
        for _ in range(n):
            x1 = float(input[ptr])
            y1 = float(input[ptr + 1])
            x2 = float(input[ptr + 2])
            y2 = float(input[ptr + 3])
            ptr += 4
            a = Point(x1, y1)
            b = Point(x2, y2)
            segments.append((a, b))
        
        # 线段略微延长，避免端点处的精度问题
        extended_segments = []
        for a, b in segments:
            dir = b - a
            length = dir.length()
            if length < 1e-10:
                continue  # 无效线段，题目保证不会出现
            dir = dir.scale(1e-5 / length)  # 微小扩展
            new_a = a - dir
            new_b = b + dir
            extended_segments.append((new_a, new_b))
        
        # 判断是否能封印
        if can_escape(extended_segments):
            print("no")
        else:
            print("yes")

if __name__ == "__main__":
    main()  

代码解释

1. 几何基础类：定义了Point类，实现了向量运算（减法、叉积、点积等），用于几何计算。
2. 线段相交判断：segments_intersect函数判断两线段是否相交，处理了标准情况和特殊情况（共线或端点在另一条线段上）。
3. 点在线段上判断：point_on_segment函数检查点是否在线段上（不包括端点）。
4. 路径判断：can_escape函数构建图并使用BFS算法判断原点和无穷远点是否连通。
5. 主函数：读取输入，处理线段数据，调用判断函数并输出结果。

该代码通过构建几何模型和图结构，利用BFS算法高效地解决了封印判断问题，确保了在存在封闭区域时能够正确识别。

题意分析

本题描述了一位巫师Aranyaka Gondlir为了封印不死怪物，使用魔法杖画直线形成屏障墙来制造怪物陷阱的故事。任务是编写程序判断巫师是否成功地用这些直线段将位于原点 (0, 0) 的怪物封印起来，即判断这些线段所构成的屏障墙是否存在漏洞。

输入包含多组数据，每组数据首先给出一个正整数 n，表示巫师画出的线段数量。随后的 n 行，每行包含四个整数 x, y, x0, y0，代表线段两个端点的坐标。所有线段长度不为零，n 不超过100，坐标范围在 -50 到 50 之间，且任意两条线段最多有一个交点，没有三条线段共享同一个交点，任意两个交点之间的距离大于 10^-5，巫师不会画出穿过原点的线。输入以包含零的行结束。

输出对于每组数据，若怪物被成功封印，输出 yes；若存在漏洞，输出 no。

解题思路

1. 数据处理：读取输入的线段端点坐标，将其存储为点和线段信息。为了避免精度问题，对线段端点进行微小的偏移处理。
2. 构建可达性图：收集所有可能的关键点（线段端点和两个特殊点 (0, 0) 与 (inf, inf)），并检查这些点是否满足不在线段上的条件。然后，对于任意两个关键点，检查它们之间的连线是否与任何线段相交，如果不相交，则在图中添加这两个点之间的边。
3. 判断封印情况：使用广度优先搜索（BFS）算法从原点 (0, 0) 开始搜索，看是否能够到达点 (inf, inf)。如果可以到达，说明存在漏洞，怪物可以逃脱，输出 no；否则，输出 yes。

复杂度分析

1. 时间复杂度：
   • 输入处理部分，读取 n 条线段的时间复杂度为 $O(n)$。
   • 构建可达性图时，需要遍历所有关键点对，关键点数量最多为 $2n + 2$，对于每对关键点，需要检查是否与 n 条线段相交，因此构建图的时间复杂度为 $O((2n + 2)^2 \times n)$。
   • BFS 搜索的时间复杂度为 $O(V + E)$，其中 $V$ 是关键点的数量，$E$ 是图中的边数，最坏情况下 $E$ 可以达到 $V^2$，因此 BFS 的时间复杂度为 $O((2n + 2)^2)$。
   • 总体时间复杂度为 $O((2n + 2)^2 \times n)$。
2. 空间复杂度：
   • 存储线段端点和关键点需要 $O(n)$ 的空间。
   • 图的邻接表表示需要 $O(V + E)$ 的空间，最坏情况下为 $O((2n + 2)^2)$。
   • 广度优先搜索使用的队列和标记数组需要 $O(V)$ 的空间，即 $O(2n + 2)$。
   • 总体空间复杂度为 $O((2n + 2)^2)$。

代码实现

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <complex>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> pii;
const double pi = 4 * atan(1);
const double eps = 1e-10;

inline int dcmp(double x) { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; }
inline double getDistance(double x, double y) { return sqrt(x * x + y * y); }
inline double torad(double deg) { return deg / 180 * pi; }

struct Point {
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void write() { printf("%lf %lf", x, y); }

    bool operator == (const Point& u) const { return dcmp(x - u.x) == 0 && dcmp(y - u.y) == 0; }
    bool operator != (const Point& u) const { return !(*this == u); }
    bool operator < (const Point& u) const { return x < u.x || (x == u.x && y < u.y); }
    bool operator > (const Point& u) const { return u < *this; }
    bool operator <= (const Point& u) const { return *this < u || *this == u; }
    bool operator >= (const Point& u) const { return *this > u || *this == u; }
    Point operator + (const Point& u) { return Point(x + u.x, y + u.y); }
    Point operator - (const Point& u) { return Point(x - u.x, y - u.y); }
    Point operator * (const double u) { return Point(x * u, y * u); }
    Point operator / (const double u) { return Point(x / u, y / u); }
    double operator * (const Point& u) { return x * u.y - y * u.x; }
};
typedef Point Vector;
typedef vector<Point> Polygon;

struct Line {
    double a, b, c;
    Line(double a = 0, double b = 0, double c = 0): a(a), b(b), c(c) {}
};

struct DirLine {
    Point p;
    Vector v;
    double ang;
    DirLine() {}
    DirLine(Point p, Vector v): p(p), v(v) { ang = atan2(v.y, v.x); }
    bool operator < (const DirLine& u) const { return ang < u.ang; }
};

struct Circle {
    Point o;
    double r;
    Circle() {}
    Circle(Point o, double r = 0): o(o), r(r) {}
    void read() { o.read(), scanf("%lf", &r); }
    Point point(double rad) { return Point(o.x + cos(rad) * r, o.y + sin(rad) * r); }
    double getArea(double rad) { return rad * r * r / 2; }
};

namespace Punctual {
    double getDistance(Point a, Point b) { double x = a.x - b.x, y = a.y - b.y; return sqrt(x * x + y * y); }
};

namespace Vectorial {
    double getDot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
    double getCross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
    double getLength(Vector a) { return sqrt(getDot(a, a)); }
    double getPLength(Vector a) { return getDot(a, a); }
    double getAngle(Vector u) { return atan2(u.y, u.x); }
    double getAngle(Vector a, Vector b) { return acos(getDot(a, b) / getLength(a) / getLength(b)); }
    Vector rotate(Vector a, double rad) { return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }
    Vector getNormal(Vector a) { double l = getLength(a); return Vector(-a.y / l, a.x / l); }
};

namespace ComplexVector {
    typedef complex<double> Point;
    typedef Point Vector;

    double getDot(Vector a, Vector b) { return real(conj(a) * b); }
    double getCross(Vector a, Vector b) { return imag(conj(a) * b); }
    Vector rotate(Vector a, double rad) { return a * exp(Point(0, rad)); }
};

namespace Linear {
    using namespace Vectorial;

    Line getLine(double x1, double y1, double x2, double y2) { return Line(y2 - y1, x1 - x2, y1 * x2 - x1 * y2); }
    Line getLine(double a, double b, Point u) { return Line(a, -b, u.y * b - u.x * a); }

    bool getIntersection(Line p, Line q, Point& o) {
        if (fabs(p.a * q.b - q.a * p.b) < eps)
            return false;
        o.x = (q.c * p.b - p.c * q.b) / (p.a * q.b - q.a * p.b);
        o.y = (q.c * p.a - p.c * q.a) / (p.b * q.a - q.b * p.a);
        return true;
    }

    bool getIntersection(Point p, Vector v, Point q, Vector w, Point& o) {
        if (dcmp(getCross(v, w)) == 0) return false;
        Vector u = p - q;
        double k = getCross(w, u) / getCross(v, w);
        o = p + v * k;
        return true;
    }

    double getDistanceToLine(Point p, Point a, Point b) { return fabs(getCross(b - a, p - a) / getLength(b - a)); }
    double getDistanceToSegment(Point p, Point a, Point b) {
        if (a == b) return getLength(p - a);
        Vector v1 = b - a, v2 = p - a, v3 = p - b;
        if (dcmp(getDot(v1, v2)) < 0) return getLength(v2);
        else if (dcmp(getDot(v1, v3)) > 0) return getLength(v3);
        else return fabs(getCross(v1, v2) / getLength(v1));
    }

    Point getPointToLine(Point p, Point a, Point b) { Vector v = b - a; return a + v * (getDot(v, p - a) / getDot(v, v)); }

    bool haveIntersection(Point a1, Point a2, Point b1, Point b2) {
        double c1 = getCross(a2 - a1, b1 - a1), c2 = getCross(a2 - a1, b2 - a1), c3 = getCross(b2 - b1, a1 - b1), c4 = getCross(b2 - b1, a2 - b1);
        return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
    }

    bool onSegment(Point p, Point a, Point b) { return dcmp(getCross(a - p, b - p)) == 0 && dcmp(getDot(a - p, b - p)) < 0; }
    bool onLeft(DirLine l, Point p) { return dcmp(l.v * (p - l.p)) > 0; }
}

namespace Triangular {
    using namespace Vectorial;

    double getAngle(double a, double b, double c) { return acos((a * a + b * b - c * c) / (2 * a * b)); }
    double getArea(double a, double b, double c) { double s = (a + b + c) / 2; return sqrt(s * (s - a) * (s - b) * (s - c)); }
    double getArea(double a, double h) { return a * h / 2; }
    double getArea(Point a, Point b, Point c) { return fabs(getCross(b - a, c - a)) / 2; }
    double getDirArea(Point a, Point b, Point c) { return getCross(b - a, c - a) / 2; }
};

namespace Polygonal {
    using namespace Vectorial;
    using namespace Linear;

    double getArea(Point* p, int n) {
        double ret = 0;
        for (int i = 1; i < n - 1; i++)
            ret += getCross(p[i] - p[0], p[i + 1] - p[0]);
        return fabs(ret) / 2;
    }

    int getConvexHull(Point* p, int n, Point* ch) {
        sort(p, p + n);
        int m = 0;
        for (int i = 0; i < n; i++) {
            while (m > 1 && dcmp(getCross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 1])) <= 0) m--;
            ch[m++] = p[i];
        }
        int k = m;
        for (int i = n - 2; i >= 0; i--) {
            while (m > k && dcmp(getCross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) <= 0) m--;
            ch[m++] = p[i];
        }
        if (n > 1) m--;
        return m;
    }

    int isPointInPolygon(Point o, Point* p, int n) {
        int wn = 0;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            if (onSegment(o, p[i], p[j])) return 0;
            int k = dcmp(getCross(p[j] - p[i], o - p[i]));
            int d1 = dcmp(p[i].y - o.y);
            int d2 = dcmp(p[j].y - o.y);
            if (k > 0 && d1 <= 0 && d2 > 0) wn++;
            if (k < 0 && d2 <= 0 && d1 > 0) wn--;
        }
        return wn ? -1 : 1;
    }

    void rotatingCalipers(Point *p, int n, vector<pii>& sol) {
        sol.clear();
        int j = 1; p[n] = p[0];
        for (int i = 0; i < n; i++) {
            while (getCross(p[j + 1] - p[i + 1], p[i] - p[i + 1]) > getCross(p[j] - p[i + 1], p[i] - p[i + 1]))
                j = (j + 1) % n;
            sol.push_back(make_pair(i, j));
            sol.push_back(make_pair(i + 1, j + 1));
        }
    }

    Polygon CutPolygon(Polygon u, Point a, Point b) {
        Polygon ret;
        int n = u.size();
        for (int i = 0; i < n; i++) {
            Point c = u[i], d = u[(i + 1) % n];
            if (dcmp((b - a) * (c - a)) >= 0) ret.push_back(c);
            if (dcmp((b - a) * (c - d)) != 0) {
                Point t;
                getIntersection(a, b - a, c, d - c, t);
                if (onSegment(t, c, d))
                    ret.push_back(t);
            }
        }
        return ret;
    }

    int halfPlaneIntersection(DirLine* li, int n, Point* poly) {
        sort(li, li + n);

        int first, last;
        Point* p = new Point[n];
        DirLine* q = new DirLine[n];
        q[first = last = 0] = li[0];

        for (int i = 1; i < n; i++) {
            while (first < last && !onLeft(li[i], p[last - 1])) last--;
            while (first < last && !onLeft(li[i], p[first])) first++;
            q[++last] = li[i];

            if (dcmp(q[last].v * q[last - 1].v) == 0) {
                last--;
                if (onLeft(q[last], li[i].p)) q[last] = li[i];
            }

            if (first < last)
                getIntersection(q[last - 1].p, q[last - 1].v, q[last].p, q[last].v, p[last - 1]);
        }

        while (first < last && !onLeft(q[first], p[last - 1])) last--;
        if (last - first <= 1) return 0;
        getIntersection(q[last].p, q[last].v, q[first].p, q[first].p, p[last]);

        int m = 0;
        for (int i = first; i <= last; i++) poly[m++] = p[i];
        return m;
    }
};

namespace Circular {
    using namespace Linear;
    using namespace Vectorial;
    using namespace Triangular;

    int getLineCircleIntersection(Point p, Point q, Circle O, double& t1, double& t2, vector<Point>& sol) {
        Vector v = q - p;
        double a = v.x, b = p.x - O.o.x, c = v.y, d = p.y - O.o.y;
        double e = a * a + c * c, f = 2 * (a * b + c * d), g = b * b + d * d - O.r * O.r;
        double delta = f * f - 4 * e * g;
        if (dcmp(delta) < 0) return 0;
        if (dcmp(delta) == 0) {
            t1 = t2 = -f / (2 * e);
            sol.push_back(p + v * t1);
            return 1;
        }

        t1 = (-f - sqrt(delta)) / (2 * e); sol.push_back(p + v * t1);
        t2 = (-f + sqrt(delta)) / (2 * e); sol.push_back(p + v * t2);
        return 2;
    }

    int getCircleCircleIntersection(Circle o1, Circle o2, vector<Point>& sol) {
        double d = getLength(o1.o - o2.o);

        if (dcmp(d) == 0) {
            if (dcmp(o1.r - o2.r) == 0) return -1;
            return 0;
        }

        if (dcmp(o1.r + o2.r - d) < 0) return 0;
        if (dcmp(fabs(o1.r - o2.r) - d) > 0) return 0;

        double a = getAngle(o2.o - o1.o);
        double da = acos((o1.r * o1.r + d * d - o2.r * o2.r) / (2 * o1.r * d));

        Point p1 = o1.point(a - da), p2 = o1.point(a + da);

        sol.push_back(p1);
        if (p1 == p2) return 1;
        sol.push_back(p2);
        return 2;
    }

    int getTangents(Point p, Circle o, Vector* v) {
        Vector u = o.o - p;
        double d = getLength(u);
        if (d < o.r) return 0;
        else if (dcmp(d - o.r) == 0) {
            v[0] = rotate(u, pi / 2);
            return 1;
        } else {
            double ang = asin(o.r / d);
            v[0] = rotate(u, -ang);
            v[1] = rotate(u, ang);
            return 2;
        }
    }

    int getTangents(Circle o1, Circle o2, Point* a, Point* b) {
        int cnt = 0;
        if (o1.r < o2.r) { swap(o1, o2); swap(a, b); }
        double d2 = getLength(o1.o - o2.o); d2 = d2 * d2;
        double rdif = o1.r - o2.r, rsum = o1.r + o2.r;
        if (d2 < rdif * rdif) return 0;
        if (dcmp(d2) == 0 && dcmp(o1.r - o2.r) == 0) return -1;

        double base = getAngle(o2.o - o1.o);
        if (dcmp(d2 - rdif * rdif) == 0) {
            a[cnt] = o1.point(base); b[cnt] = o2.point(base); cnt++;
            return cnt;
        }

        double ang = acos((o1.r - o2.r) / sqrt(d2));
        a[cnt] = o1.point(base + ang); b[cnt] = o2.point(base + ang); cnt++;
        a[cnt] = o1.point(base - ang); b[cnt] = o2.point(base - ang); cnt++;

        if (dcmp(d2 - rsum * rsum) == 0) {
            a[cnt] = o1.point(base); b[cnt] = o2.point(base); cnt++;
        } else if (d2 > rsum * rsum) {
            double ang = acos((o1.r + o2.r) / sqrt(d2));
            a[cnt] = o1.point(base + ang); b[cnt] = o2.point(base + ang); cnt++;
            a[cnt] = o1.point(base - ang); b[cnt] = o2.point(base - ang); cnt++;
        }
        return cnt;
    }

    Circle CircumscribedCircle(Point p1, Point p2, Point p3) {
        double Bx = p2.x - p1.x, By = p2.y - p1.y;
        double Cx = p3.x - p1.x, Cy = p3.y - p1.y;
        double D = 2 * (Bx * Cy - By * Cx);
        double cx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x;
        double cy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y;
        Point p = Point(cx, cy);
        return Circle(p, getLength(p1 - p));
    }

    Circle InscribedCircle(Point p1, Point p2, Point p3) {
        double a = getLength(p2 - p3);
        double b = getLength(p3 - p1);
        double c = getLength(p1 - p2);
        Point p = (p1 * a + p2 * b + p3 * c) / (a + b + c);
        return Circle(p, getDistanceToLine(p, p1, p2));
    }

    double getPublicAreaToTriangle(Circle O, Point a, Point b) {
        if (dcmp((a - O.o) * (b - O.o)) == 0) return 0;
        int sig = 1;
        double da = getPLength(O.o - a), db = getPLength(O.o - b);
        if (dcmp(da - db) > 0) {
            swap(da, db);
            swap(a, b);
            sig = -1;
        }

        double t1, t2;
        vector<Point> sol;
        int n = getLineCircleIntersection(a, b, O, t1, t2, sol);

        if (dcmp(da - O.r * O.r) <= 0) {
            if (dcmp(db - O.r * O.r) <= 0) return getDirArea(O.o, a, b) * sig;

            int k = 0;
            if (getPLength(sol[0] - b) > getPLength(sol[1] - b)) k = 1;

            double ret = getArea(O.o, a, sol[k]) + O.getArea(getAngle(sol[k] - O.o, b - O.o));
            double tmp = (a - O.o) * (b - O.o);
            return ret * sig * dcmp(tmp);
        }

        double d = getDistanceToSegment(O.o, a, b);
        if (dcmp(d - O.r) >= 0) {
            double ret = O.getArea(getAngle(a - O.o, b - O.o));
            double tmp = (a - O.o) * (b - O.o);
            return ret * sig * dcmp(tmp);
        }


        double k1 = O.r / getLength(a - O.o), k2 = O.r / getLength(b - O.o);
        Point p = O.o + (a - O.o) * k1, q = O.o + (b - O.o) * k2;
        double ret1 = O.getArea(getAngle(p - O.o, q - O.o));
        double ret2 = O.getArea(getAngle(sol[0] - O.o, sol[1] - O.o)) - getArea(O.o, sol[0], sol[1]);
        double ret = (ret1 - ret2), tmp = (a - O.o) * (b - O.o);
        return ret * sig * dcmp(tmp);
    }

    double getPublicAreaToPolygon(Circle O, Point* p, int n) {
        if (dcmp(O.r) == 0) return 0;
        double area = 0;
        for (int i = 0; i < n; i++) {
            int u = (i + 1) % n;
            area += getPublicAreaToTriangle(O, p[i], p[u]);
        }
        return fabs(area);
    }
};

using namespace Vectorial;
using namespace Polygonal;

const int maxn = 1005;
const double bw = 1e-5;
const double inf = 1000.0;

int N, M, V[maxn];
Point L[maxn], R[maxn];
vector<Point> S;
vector<int> G[maxn];

bool check(Point t) {
    for (int i = 0; i < N; i++)
        if (dcmp(getCross(L[i] - t, R[i] - t)) == 0 && dcmp(getDot(L[i] - t, R[i] - t)) < 0)
            return false;
    return true;
}

void init() {
    for (int i = 0; i < N; i++) {
        L[i].read(), R[i].read();
        Point tmp = (R[i] - L[i]) / getLength(L[i] - R[i]);
        L[i] = L[i] - tmp * bw;
        R[i] = R[i] + tmp * bw;
    }

    S.clear();
    S.push_back(Point(0, 0));
    S.push_back(Point(inf, inf));
    for (int i = 0; i < N; i++) {
        if (check(L[i])) S.push_back(L[i]);
        if (check(R[i])) S.push_back(R[i]);
    }

    M = S.size();
    for (int i = 0; i < M; i++)
        G[i].clear();

    for (int i = 0; i < M; i++) {
        for (int j = i + 1; j < M; j++) {
            bool flag = true;
            for (int k = 0; k < N; k++)
                if (haveIntersection(S[i], S[j], L[k], R[k])) {
                    flag = false;
                    break;
                }
            if (flag) {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
}

int bfs(int s, int e) {
    queue<int> Q;
    memset(V, 0, sizeof(V));

    Q.push(s);
    V[s] = 1;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            if (V[G[u][i]]) continue;
            V[G[u][i]] = 1;
            Q.push(G[u][i]);
        }
    }
    return !V[e];
}

int main() {
    while (scanf("%d", &N) == 1 && N) {
        init();
        printf("%s\n", bfs(0, 1) ? "yes" : "no");
    }
    return 0;
}