编程之美(七)光影切割问题

在一个平面内有一个矩形区域，直线穿过矩形可以将其分割为不同的区域，且在这个平面中不存在三条直线相交一点的情况。求当有N条直线穿过矩形时，它被分割为多少个区域？

例如： 图中有两条直线将矩形分割为 $4$ 个区域。

分析与思路

思路一

两条直线：$1$个交点，$4$个区域 三条直线：$2$个交点，$6$个区域 三条直线：$3$个交点，$7$个区域 四条直线：$4$个交点，$9$个区域 四条直线：$5$个交点，$10$个区域

由此可以推出：$num=N+m+1$($num$表示区域数，$N$表示直线数，$m$表示交点数) 思路：用两点式表示一条直线，通过该直线可求出与其它直线的交点，判断该交点是否落在($A,B$)范围内，如果是则$+1$，得到交点数$cnt$，并推出最终的区域数：$cnt+N+1$

思路二

思路：由上图，可知右边直线的顺序为($c,b,a$)，形成的逆序对为($c,b$), ($c,a$), ($b,a$)，恰巧为其交点的数量；当我们已知右边直线的序列，我们只需求逆序对数目即可得出其交点数量，然后按照思路一的推导可得出区域数

逆序对数目求法：归并排序的思想；在归并排序的过程中比较start与mid + 1的大小，从而求出逆序对的数量

类似题目：【剑指offer】数组中的逆序对

代码

思路一

#include <iostream> using namespace std; #define Left 0 #define Right 9 typedef struct node { double x1, y1, x2, y2; }line; line test_lines[] = {{1, 1, 2, 2}, {0, 3, 9, 2}, {0, 4, 9, 7}, {0, 1, 9, 3}}; int test_len = 4; //line test_lines[] = {{2, 1, 5, 1}, {5, 5, 8, 5}, {8, 1, 2, 7}}; //int test_len = 3; bool judge(line line1, line line2, double &x, double &y) { double k1 = 0, b1 = 0, k2 = 0, b2 = 0; if (line1.x1 - line1.x2 != 0 && line2.x1 - line2.x2 != 0) { k1 = (line1.y1 - line1.y2) / (line1.x1 - line1.x2); k2 = (line2.y1 - line2.y2) / (line2.x1 - line2.x2); if (k1 == k2) return false; b1 = line1.y1 - k1 * line1.x1; b2 = line2.y1 - k2 * line2.x1; x = (b2 - b1) / (k1 - k2); y = k1 * x + b1; } else if (line1.x1 - line1.x2 == 0 && line2.x1 - line2.x2 == 0) return false; else if (line1.x1 - line1.x2 == 0 && line2.x1 - line2.x2 != 0) { k2 = (line2.y1 - line2.y2) / (line2.x1 - line2.x2); b2 = line2.y1 - k2 * line2.x1; x = line1.x1; y = k2 * x + b2; } else if (line1.x1 - line1.x2 != 0 && line2.x1 - line2.x2 == 0) { k1 = (line1.y1 - line1.y2) / (line1.x1 - line1.x2); b1 = line1.y1 - k1 * line1.x1; x = line2.x1; y = k1 * x + b1; } return true; } int Cal(line test_lines[], int test_len) { double x, y; int cnt = 0; for (int i = 0; i < test_len; ++i) { for (int j = i + 1; j < test_len; ++j) { bool flag = judge(test_lines[i], test_lines[j], x, y); if ( flag && x > Left && x < Right && y > Left && y < Right) { cout << x << " " << y << endl; cnt++; } } } cnt += test_len + 1; return cnt; } int main() { int num = Cal(test_lines, test_len); cout << num << endl; return 0; }

测试结果：

line test_lines[] = {{1, 1, 2, 2}, {0, 3, 9, 2}, {0, 4, 9, 7}, {0, 1, 9, 3}}; int test_len = 4;

line test_lines[] = {{2, 1, 5, 1}, {5, 5, 8, 5}, {8, 1, 2, 7}}; int test_len = 3;

思路二

#include <iostream> using namespace std; int test_line[] = {4, 1, 3, 2}; int len = 4; //int test_line[] = {3, 1, 4, 2, 7, 6, 8, 5}; //int len = 8; int getInverse(int test_line[], int start, int end) { if (start < end) { int mid = (start + end) >> 1; int left = getInverse(test_line, start, mid); int right = getInverse(test_line, mid + 1, end); int k = 0; int* copy = new int[end - start + 1]; int i = start, j = mid + 1; int cnt = 0; while (i <= mid && j <= end) { if (test_line[i] > test_line[j]) { cnt += mid - i + 1; copy[k++] = test_line[j++]; } else { copy[k++] = test_line[i++]; } } while (i <= mid) copy[k++] = test_line[i++]; while (j <= end) copy[k++] = test_line[j++]; k = 0; for (int i = start; i <= end; ++i) test_line[i] = copy[k++]; delete []copy; return left + right + cnt; } else { return 0; } } int main() { int num = getInverse(test_line, 0, len - 1); for (int i = 0; i < len; ++i) cout << test_line[i] << " "; cout << endl << num + len + 1 << endl; return 0; }

测试结果：

int test_line[] = {4, 1, 3, 2}; int len = 4;

int test_line[] = {3, 1, 4, 2, 7, 6, 8, 5}; int len = 3;