013几何数学——算法备赛

几何数学

平面切分

蓝桥杯2020年省赛题

问题描述

平面上有N条直线，其中第i条直线为y=Ax+B.请计算这些直线将平面分成了几个部分？

输入

第一行输入一个N，接下来N行输入两个整数代表Ai和Bi。

1<=N<=10^5.

思路分析

初始时一条直线将平面分为2个部分。

而后每添加一条直线

• 与前面某个直线重合，将平面多划分0个部分

• 与前面直线有x个交叉点，将平面多划分x+1个部分。

• 与前面直线有0个交叉点，与前面直线平行，将平面多划分1个部分

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int n; cin>>n;vector<pair<int,int>>d(n);for(int i=0;i<n;i++){cin>>d[i].first>>d[i].second;}long long ans=2;  //初始时一条线将平面分为两个部分for(int i=1;i<n;i++){unordered_map<double,unordered_set<double>>mp;  //mp[k]表示交叉点x=k的不同的y的集合auto [a,b]=d[i];bool vis=0;int s=0;for(int j=0;j<i;j++){  //对前面的线求交叉点auto [a1,b1]=d[j];if(a==a1){if(b!=b1){vis=true;  //与前面线平行，寻找下一个continue;} else{s=-1; break;  //与前面的线重叠}}double x=(double)(b-b1)/(a-a1);  //交叉点xdouble y=(double)(a*b1-a1*b)/(a-a1);  //交叉点yif(mp[x].count(y)) continue;  //前面统计过这个交叉点，不重复统计else{s++;mp[x].insert(y);}}if(s) ans+=s+1;else ans+=vis;  //没有新交叉点，与前面线平行}cout<<ans;return 0;
}

直线上最多的点

问题描述

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

原题链接

暴力枚举直线

我们知道，两点可以确定一条线。

一个朴素的做法是先枚举两点（确定一条线），然后检查其余点是否落在该线中。

为避免除法精度问题，当我们枚举两个点 x 和 y 时，不直接计算其对应直线的 斜率和 截距。

而是通过判断 x 和 y 与第三个点 p 形成的两条直线斜率是否相等，来得知点 p 是否落在该直线上。
$$详细说，当给定两个点(x_1,y_1)和(x_2,y_2)时，对应斜率\frac{x_2-x_1}{y_2-y_1}$$

$$为避免计算机除法的精度问题，我们将判定\frac{x_1-x_2}{y_1-y_2}=\frac{x_2-x_3}{y_2-y_3}改为判定(x_1-x_2)\ast (y_2-y_3)=(x_2-x_3)\ast (y_1-y_2)是否成立$$

这样一来，将存在精度问题的「除法判定」巧妙转为「乘法判定」。

时间复杂度O(n^3)

代码

class Solution {
public:int maxPoints(vector<vector<int>>& points) {int n = points.size(), ans = 1;for (int i = 0; i < n; i++) {vector<int> x = points[i];for (int j = i + 1; j < n; j++) {vector<int> y = points[j];// 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上int cnt = 2;for (int k = j + 1; k < n; k++) {vector<int> p = points[k];int s1 = (y[1] - x[1]) * (p[0] - y[0]);int s2 = (p[1] - y[1]) * (y[0] - x[0]);if (s1 == s2) cnt++;}ans = max(ans, cnt);}}return ans;}
};
作者：宫水三叶

根据「朴素解法」的思路，枚举所有直线的过程不可避免，但统计点数的过程可以优化。

具体的，我们可以先枚举所有可能出现的 直线斜率（根据两点确定一条直线，即枚举所有的「点对」），使用「哈希表」统计所有 斜率 对应的点的数量，在所有值中取 max 即是答案。

一些细节：在使用「哈希表」进行保存时，为了避免精度问题，我们直接使用字符串进行保存，同时需要将 斜率 约干净。

int maxPoints(vector<vector<int>>& points) {int n = points.size(), ans = 1;for (int i = 0; i < n; i++) {unordered_map<string, int> map;  //map放置在内层循环中，而不是全局的，固定一个点,保证平行的线不会统计到一起int maxv = 0;int x1 = points[i][0], y1 = points[i][1];for (int j = i + 1; j < n; j++) {int x2 = points[j][0], y2 = points[j][1];int a = x1 - x2, b = y1 - y2;int k = gcd(a, b);string key = to_string(a / k) + "_" + to_string(b / k);  //无斜率直线为"0_1",斜率为0直线为"1_0"map[key]++;maxv = max(maxv, map[key]);}ans = max(ans, maxv + 1);}return ans;}int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

矩形面积

问题描述

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

• 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
• 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

原题链接

代码

int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {int sum1=(ax2-ax1)*(ay2-ay1);int sum2=(bx2-bx1)*(by2-by1);int x = max(0, min(ax2, bx2) - max(ax1, bx1));  //重叠的x轴长度int y = max(0, min(ay2, by2) - max(ay1, by1));  //重叠的y轴的长度return sum1+sum2-x1*x2;  //总面积减重叠部分
}

在圆内生成随机点

问题描述

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

原题链接

代码

class Solution {double r, x, y;Random random = new Random();public Solution(double _r, double _x, double _y) {r = _r; x = _x; y = _y;}public double[] randPoint() {double len = Math.sqrt(random.nextDouble(r * r)), ang = random.nextDouble(2 * Math.PI);double nx = x + len * Math.cos(ang), ny = y + len * Math.sin(ang);return new double[]{nx, ny};}
}作者：宫水三叶