[C++知识库] 【蓝桥杯】第十二届省赛b组（c/c++）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【蓝桥杯】第十二届省赛b组（c/c++） -> 正文阅读

[C++知识库]【蓝桥杯】第十二届省赛b组（c/c++）

在这里插入图片描述

解题思路

题意为求直线数目，重叠直线算同一条直线
直线表达：
两点式方程：（x - x1 ）/（x2 - x1）=（y - y1）/（y2 - y1）
化为Ax+By+c=0形式为：（y2 - y1）x + （x2 - x1）y - x1y2 + x2y1 = 0
储存A、B、C（除以公约数后的），并利用集合set去重

ac代码

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef pair<int, int> P2;
typedef pair<P2, int> P3;
set<P3> s;
vector<P2> v;//可以将pair作为vector的元素 

int main() {
	int x, y;
	cin >> x >> y;

	for(int i = 0; i < x; i++) {
		for(int j = 0; j < y; j++) {
			v.push_back({i,j});//pair构建方式 
		}
	}//得到所有的点

	for(int i = 0; i < v.size(); i++) { //双重for循环，非重复遍历
		for(int j = i + 1; j < v.size(); j++) {
			int x1 = v[i].first, y1 = v[i].second;
			int x2 = v[j].first, y2 = v[j].second;
			int A = y1 - y2, B = x2 - x1, C = -x1 * y2 + x2 * y1;
			int gcd = __gcd(__gcd(A,B) , C);
			s.insert({{B / gcd, A / gcd}, C / gcd});
		}
	}

	cout << s.size();
	return 0;
}