P8720 [蓝桥杯 2020 省 B2] 平面切分--set、pair

题目

分析

大佬写的很明白，看这儿

我讲讲其中用到的知识点吧！

一、pair

pair是 C++ 中的一个模板类，用于存储两个值（可以是不同类型）。

1、基本用法

#include <iostream>
#include <utility> // pair 的头文件
using namespace std;

int main() {
    pair<int, string> student = {18, "小明"}; // 存储年龄和姓名
    cout << "年龄: " << student.first << endl;   // 输出 18
    cout << "姓名: " << student.second << endl;  // 输出 小明
    return 0;
}

2、核心特性：
pair 中的两个值可以是不同类型（如 int 和 string）。
通过 .first 和 .second 访问两个值。

3、pair 的常见用途

1）存储关联数据
例如，存储一个点的坐标 (x, y)

pair<double, double> point = {3.14, 2.71};

2）函数返回两个值

pair<bool, int> checkValue(int x) {
    if (x > 0) return {true, x};
    else return {false, 0};
}

1.1pair与vector的区别

1.2 两者使用场景

对pair:

1. 坐标 (x, y)。
2. 一个学生的年龄和姓名 (int, string)

对vector:

需要存储一组同类型数据，例如：
学生成绩列表 [90, 85, 95]。
一组字符串 [“apple”, “banana”, “cherry”]。

两者组合使用

vector<pair<double, double>> points;
points.push_back({1.0, 2.0}); // 添加点 (1.0, 2.0)
points.push_back({3.0, 4.0}); // 添加点 (3.0, 4.0)

// 遍历所有点
for (auto p : points) {
    cout << "x: " << p.first << ", y: " << p.second << endl;
}

二、set

set是 C++ 中的一个重要容器，用于存储一组唯一且有序的元素。set 是 C++ 中的一个重要容器，用于存储一组唯一且有序的元素。它的核心特性是自动去重和自动排序，非常适合处理需要唯一性和顺序性的数据。

2.1核心特点

2.2set的基本操作

(1) 创建 set

#include <set>
using namespace std;

set<int> s1;                // 默认升序排列的整数集合
set<string> s2;             // 字符串集合
set<pair<int, int>> s3;     // 存储 pair 的集合

(2) 插入元素

s1.insert(3);       // 插入元素 3
s1.insert(1);       // 插入元素 1
s1.insert(2);       // 插入元素 2
s1.insert(3);       // 重复插入 3，会被自动忽略
// 此时 s1 = {1, 2, 3}

(3) 遍历 set

//若set<pair<int,int>> s1;
//for(auto &i:s1) cout<<num;
for (auto num : s1) {
    cout << num << " ";   // 输出 1 2 3
}

(4) 查找元素

auto it = s1.find(2);
if (it != s1.end()) {
    cout << "元素 2 存在！" << endl;
}

(5) 删除元素

s1.erase(2);        // 删除元素 2
s1.erase(s1.begin()); // 删除第一个元素（即 1）

2.3 set vs unordered_set

示例：统计唯一单词数

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<string> uniqueWords;
    string word;
    
    while (cin >> word) {  // 输入单词，按 Ctrl+Z (Windows) 或 Ctrl+D (Mac) 结束
        uniqueWords.insert(word);
    }
    
    cout << "唯一单词数: " << uniqueWords.size() << endl;
    return 0;
}
//输入：apple banana apple cherry banana
//输出：唯一单词数: 3

代码

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n;
typedef pair<long double, long double> DL;
set<DL> f;
DL a[1010];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k, b;
		cin >> k >> b;
		f.insert({k, b});
	}
	int cnt = 0;
	for (auto &i : f) {
		a[cnt++] = i;
	}
	int ans = 1;
	for (int i = 0; i < cnt; i++) {
		set<DL> d;
		for (int j = 0; j < i; j++) {
			long double k1 = a[i].first;
			long double b1 = a[i].second;
			long double k2 = a[j].first;
			long double b2 = a[j].second;
			if (k1 == k2)
				continue;
		//注意，交点的x,y值是浮点型，别定义成int了！！！
			long double x = (b2 - b1) / (k1 - k2);
			long double y = k1 * x + b1;
			d.insert({x, y});
		}
		ans += d.size() + 1;
	}
	cout << ans << endl;
	return 0;
}