I Conduit!

张美清 LV 3 @ 2025-5-13 11:15:04

题目描述

Irv Kenneth Diggit 需要整合多张地下管线分布图，计算所有线段叠加后需要绘制的最少线段数量。每条线段由两个端点 $(x1, y1)$ 和 $(x2, y2)$ 定义，坐标范围为 $[0.0, 1000.0]$ ，最多两位小数。目标是合并所有共线且重叠的线段，使得最终线段数量最少。

输入格式

多组数据，每组以整数 $n$ （线段数量）开头，后跟 $n$ 行线段数据（格式：x1 y1 x2 y2）。
输入以 0 结束。

输出格式

每组数据输出一个整数，表示合并后的最少线段数量。

解题思路

关键问题

线段合并条件：两条线段必须共线且有重叠部分才能合并。
共线判定：两条线段斜率相同且在一条直线上。
重叠判定：两条共线线段在坐标轴上的投影有交集。

算法选择

线段归一化：将每条线段的两个端点按字典序排序，便于后续处理。
共线分组：使用哈希表将共线线段分组，键为线段的标准化表示（如直线方程 $ax + by + c = 0$ 的系数）。
合并重叠线段：对每组共线线段，按某一坐标轴排序后，用贪心算法合并所有重叠的线段。

步骤详解

预处理每条线段：
- 确保 $(x1, y1)$ 字典序小于 $(x2, y2)$ ，避免方向不一致导致误判。
- 计算直线方程 $ax + by + c = 0$ 的系数（需处理垂直线和水平线）。
共线分组：
- 将直线方程系数归一化（如保证 $a \geq 0$ 且 $a, b, c$ 互质），作为哈希键。
合并共线线段：
- 对每组共线线段，按 $x1$ （或 $y1$ 如果垂直线）排序。
- 遍历排序后的线段，合并所有重叠的线段。

代码实现（C++）

#include <iostream>
#include <algorithm>
#include <cmath>

#define EPS 1e-8
#define MAX_N 10005

using namespace std;

struct seg {
    double x1, y1, x2, y2;
    bool spe; // spe = true表示当前seg与y轴平行,否则不平行,与y轴平行时是没有斜率的
    double a, b;
} segs[MAX_N];

int n;

// 比较函数,核心思想是把没有斜率(与y轴平行)的放在有斜率的后面,把斜率小的放在斜率大的前面
// 对于具有相同斜率的seg,把与y轴交点低的放在前面
// 对于在一条线上的seg,把x坐标(当与y轴平行时比较y坐标)小的放在前面
bool compare(const seg &seg1, const seg &seg2) {
    // 两个seg都没有斜率
    if (seg1.spe && seg2.spe)
        return fabs(seg1.x1 - seg2.x1) < EPS? seg1.y1 < seg2.y1 + EPS : seg1.x1 < seg2.x2 + EPS;
    else if (seg1.spe &&!seg2.spe) return false; // 一个有斜率一个没有斜率,把有斜率的放在前面
    else if (!seg1.spe && seg2.spe) return true;
    else // 两个seg都有斜率
    {
        // 斜率相等时需要比较与y轴的交点,当焦点也相等时需要比较左端点x值的大小
        if (fabs(seg1.a - seg2.a) < EPS)
            return fabs(seg1.b - seg2.b) < EPS? seg1.x1 < seg2.x1 + EPS : seg1.b < seg2.b + EPS;
        else return seg1.a < seg2.a + EPS;
    }
}

void swap(double &d1, double &d2) {
    double temp = d1;
    d1 = d2;
    d2 = temp;
}

// 判断两个seg是否相交, type用来区分这个两个seg与y轴的平行情况,type = 0时表示与y轴平行
bool cross(const seg& seg1, const seg &seg2, bool type) {
    if (!type) return seg2.y1 <= seg1.y2;
    else return seg2.x1 <= seg1.x2;
}

int main() {
    int i;
    while (scanf("%d", &n) && n!= 0) {
        for (i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf", &segs[i].x1, &segs[i].y1, &segs[i].x2, &segs[i].y2);
            if (segs[i].x1 > segs[i].x2 + EPS) {
                swap(segs[i].x1, segs[i].x2);
                swap(segs[i].y1, segs[i].y2);
            } else if (fabs(segs[i].x1 - segs[i].x2) < EPS && segs[i].y1 > segs[i].y2 + EPS) {
                swap(segs[i].x1, segs[i].x2);
                swap(segs[i].y1, segs[i].y2);
            }
            segs[i].spe = false;
            if (fabs(segs[i].x1 - segs[i].x2) < EPS)
                segs[i].spe = true;
            else {
                segs[i].a = (segs[i].y2 - segs[i].y1) / (segs[i].x2 - segs[i].x1);
                segs[i].b = segs[i].y1 - segs[i].x1 * segs[i].a;
            }
        }
        sort(segs, segs + n, compare);
        int countv = 1;
        for (i = 1; i < n; i++) {
            // 当前seg与y轴平行其与上一个seg相交
            if (segs[i].spe && segs[i - 1].spe && fabs(segs[i].x1 - segs[i - 1].x1) < EPS
                && cross(segs[i - 1], segs[i], false)) {
                // 调整当前seg的y2
                if (segs[i].y2 < segs[i - 1].y2 + EPS)
                    segs[i].y2 = segs[i - 1].y2;
                continue;
            }
            // 当前seg不与y轴平行且与上一个seg相交
            if (!segs[i].spe &&!segs[i - 1].spe && fabs(segs[i].a - segs[i - 1].a) < EPS &&
                fabs(segs[i].b - segs[i - 1].b) < EPS && cross(segs[i - 1], segs[i], true)) {
                // 调整当前seg的x2
                if (segs[i].x2 < segs[i - 1].x2 + EPS)
                    segs[i].x2 = segs[i - 1].x2;
                continue;
            }
            // 找到一个新的不可与上一个seg合并的seg则需要为countv的值增加1
            countv++;
        }
        printf("%d\n", countv);
    }
    return 0;
}

复杂度分析

时间复杂度： $O(n \log n)$ ，主要来自排序和哈希表操作。
空间复杂度： $O(n)$ ，存储线段和分组信息。

示例解释

输入样例 1：
- 共 $3$ 条线段，其中两条共线且重叠，合并后剩余 $2$ 条。
输入样例 2：
- 两条线段共线且端点相接，合并为 $1$ 条。
输入样例 3：
- 两条线段共线但端点不完全重合，无法合并，仍为 $2$ 条。

2300170046 LV 7 @ 2025-5-5 12:16:05

题意分析

Irv 需要将多张包含地下管线信息的小地图整合成一张综合大图，为了提高效率和节省绘图仪墨水，要计算出最少的线段数量来表示所有管线。输入数据包含多组测试用例，每组用例首先给出线段的数量 n，然后是 n 条线段的端点坐标 (x1, y1) 和 (x2, y2)，坐标范围在 0.0 到 1000.0 之间且最多保留两位小数，线段数量最多为 10000，最后以单独的 0 表示输入结束。输出为每组数据整合后大图上最少的线段数量。

解题思路

线段预处理：
- 读入每条线段的端点坐标后，检查并确保 x1 <= x2，如果不满足则交换 x1 和 x2，同时交换 y1 和 y2。
- 判断线段是否与 y 轴平行（即 x1 和 x2 差值小于 EPS），如果平行则标记 spe = true，否则计算线段的斜率 a = (y2 - y1) / (x2 - x1) 和截距 b = y1 - x1 * a。
线段排序：
- 定义比较函数 compare，根据以下规则对线段进行排序：
  - 与 y 轴平行的线段放在有斜率的线段后面。
  - 对于有斜率的线段，斜率小的放在斜率大的前面。
  - 斜率相等时，与 y 轴交点低的放在前面（通过比较截距 b）。
  - 斜率和截距都相等时，x 坐标（当与 y 轴平行时比较 y 坐标）小的放在前面。
合并线段：
- 初始化合并后的线段数量 countv = 1，从第二条线段开始遍历排序后的线段数组。
- 对于当前线段和前一条线段：
  - 如果两条线段都与 y 轴平行且 x 坐标相同，并且当前线段的起点 y1 小于等于前一条线段的终点 y2，则调整当前线段的终点 y2 为前一条线段的 y2，并继续处理下一条线段。
  - 如果两条线段都不与 y 轴平行，且斜率和截距都相等，并且当前线段的起点 x1 小于等于前一条线段的终点 x2，则调整当前线段的终点 x2 为前一条线段的 x2，并继续处理下一条线段。
  - 如果当前线段不能与前一条线段合并，则 countv++。
输出结果：输出合并后的最少线段数量 countv。

复杂度分析

时间复杂度：
- 读入线段的时间复杂度为 (O(n))，其中 n 是线段的数量。
- 排序的时间复杂度为 (O(nlogn))，因为使用了标准的排序算法 sort。
- 遍历线段数组进行合并操作的时间复杂度为 (O(n))。
- 总体时间复杂度为 (O(nlogn))，主要由排序操作决定。
空间复杂度：
- 程序使用了一个大小为 n 的线段结构体数组 segs 来存储线段信息，因此空间复杂度为 (O(n))。

代码实现

#include <iostream>
#include <algorithm>
#include <cmath>

#define EPS 1e-8
#define MAX_N 10005

using namespace std;

struct seg {
    double x1, y1, x2, y2;
    bool spe; // spe = true表示当前seg与y轴平行,否则不平行,与y轴平行时是没有斜率的
    double a, b;
} segs[MAX_N];

int n;

// 比较函数,核心思想是把没有斜率(与y轴平行)的放在有斜率的后面,把斜率小的放在斜率大的前面
// 对于具有相同斜率的seg,把与y轴交点低的放在前面
// 对于在一条线上的seg,把x坐标(当与y轴平行时比较y坐标)小的放在前面
bool compare(const seg &seg1, const seg &seg2) {
    // 两个seg都没有斜率
    if (seg1.spe && seg2.spe)
        return fabs(seg1.x1 - seg2.x1) < EPS? seg1.y1 < seg2.y1 + EPS : seg1.x1 < seg2.x2 + EPS;
    else if (seg1.spe &&!seg2.spe) return false; // 一个有斜率一个没有斜率,把有斜率的放在前面
    else if (!seg1.spe && seg2.spe) return true;
    else // 两个seg都有斜率
    {
        // 斜率相等时需要比较与y轴的交点,当焦点也相等时需要比较左端点x值的大小
        if (fabs(seg1.a - seg2.a) < EPS)
            return fabs(seg1.b - seg2.b) < EPS? seg1.x1 < seg2.x1 + EPS : seg1.b < seg2.b + EPS;
        else return seg1.a < seg2.a + EPS;
    }
}

void swap(double &d1, double &d2) {
    double temp = d1;
    d1 = d2;
    d2 = temp;
}

// 判断两个seg是否相交, type用来区分这个两个seg与y轴的平行情况,type = 0时表示与y轴平行
bool cross(const seg& seg1, const seg &seg2, bool type) {
    if (!type) return seg2.y1 <= seg1.y2;
    else return seg2.x1 <= seg1.x2;
}

int main() {
    int i;
    while (scanf("%d", &n) && n!= 0) {
        for (i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf", &segs[i].x1, &segs[i].y1, &segs[i].x2, &segs[i].y2);
            if (segs[i].x1 > segs[i].x2 + EPS) {
                swap(segs[i].x1, segs[i].x2);
                swap(segs[i].y1, segs[i].y2);
            } else if (fabs(segs[i].x1 - segs[i].x2) < EPS && segs[i].y1 > segs[i].y2 + EPS) {
                swap(segs[i].x1, segs[i].x2);
                swap(segs[i].y1, segs[i].y2);
            }
            segs[i].spe = false;
            if (fabs(segs[i].x1 - segs[i].x2) < EPS)
                segs[i].spe = true;
            else {
                segs[i].a = (segs[i].y2 - segs[i].y1) / (segs[i].x2 - segs[i].x1);
                segs[i].b = segs[i].y1 - segs[i].x1 * segs[i].a;
            }
        }
        sort(segs, segs + n, compare);
        int countv = 1;
        for (i = 1; i < n; i++) {
            // 当前seg与y轴平行其与上一个seg相交
            if (segs[i].spe && segs[i - 1].spe && fabs(segs[i].x1 - segs[i - 1].x1) < EPS
                && cross(segs[i - 1], segs[i], false)) {
                // 调整当前seg的y2
                if (segs[i].y2 < segs[i - 1].y2 + EPS)
                    segs[i].y2 = segs[i - 1].y2;
                continue;
            }
            // 当前seg不与y轴平行且与上一个seg相交
            if (!segs[i].spe &&!segs[i - 1].spe && fabs(segs[i].a - segs[i - 1].a) < EPS &&
                fabs(segs[i].b - segs[i - 1].b) < EPS && cross(segs[i - 1], segs[i], true)) {
                // 调整当前seg的x2
                if (segs[i].x2 < segs[i - 1].x2 + EPS)
                    segs[i].x2 = segs[i - 1].x2;
                continue;
            }
            // 找到一个新的不可与上一个seg合并的seg则需要为countv的值增加1
            countv++;
        }
        printf("%d\n", countv);
    }
    return 0;
}

ID

1037

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

Hydro

2 条题解

题目描述

输入格式

输出格式

解题思路

关键问题

算法选择

步骤详解

代码实现（C++）

复杂度分析

示例解释

题意分析

解题思路

复杂度分析

代码实现

信息

还没有账户？

登录