第十二届蓝桥杯 2021 C/C++组 直线
目录
题目：
题目描述：
题目链接：
思路：
核心思路：
两点确定一条直线：
思路详解：
代码：
第一种方式代码详解：
第二种方式代码详解：
题目：
题目描述：
题目链接：
直线 - 蓝桥云课
思路：
核心思路：
枚举+set去重
两点确定一条直线：
第一种推导参数的方式是直接代入两点坐标到一般式中求参数。下图展示了推导过程
第二种推导参数的方式是通过两点式方程求参数。下图展示了推导过程
思路详解：
用pair<int,int>类型来存储两个值，即在枚举的时候表示平面直角坐标系中的点。再用pair<PII,int>类型来存储三个值，PII来表示直线的前两个参数A和B，int表示直线的最后一个参数C。定义一个vector容器vec,用于存储给定平面上的所有整点的坐标,元素类型是PII，定义一个set容器s,用于存储不同的直线,set容器会自动对元素进行去重,这里的元素类型是PIII,即每一条直线用PIII来表示。然后就是从vec中提取出两个点的横纵坐标并计算得到直线参数A，B，C。这里注意：为了避免同一条直线因为系数的倍数关系而被重复存储，我们要利用__gcd()最小公倍数函数对直线方程系数进行化简。将化简后的直线信息以PIII的形式插入到set容器s中，由于set会自动去重，所以最后的结果就是set容器的大小
代码：
第一种方式代码详解：
#include<bits/stdc++.h> //填空题,答案是40257
using namespace std; //思路主要就是枚举和去重,存储三个参数用pair来表示,去重用set集合 typedef pair<int,int> PII; //将pair<int,int>类型重命名为PII,方便后续代码书写,pair用于存储两个值,//这里用来表示平面直角坐标系中的点,横坐标和纵坐标都是int类型
typedef pair<PII,int> PIII; //将pair<PII,int>类型重命名为PIII,方便后续代码书写,这里PII表示直线的//一般式方程的前两个参数A和B,int表示一般式方程的最后一个参数C set<PIII> s; //定义一个set容器s,用于存储不同的直线,set容器会自动对元素进行去重,这里的元素类型是//PIII,即每一条直线用PIII来表示 vector<PII> vec; //定义一个vector容器vec,用于存储给定平面上的所有整点的坐标,元素类型是PII int main()
{for(int i=0;i<20;i++) //由题遍历横坐标0<=i<20,纵坐标0<=j<21的所有整点,将每个点的坐标(i,j)以 { //PII的形式存入vec容器中 for(int j=0;j<21;j++){vec.push_back({i,j});}}for(int i=0;i<vec.size();i++) //外层遍历vec中的每一个点(索引为i) {for(int j=i+1;j<vec.size();j++) //内层循环从i+1开始遍历(索引为j),这样可以保证每两个点只 { //合一次(避免重复计算直线,点1和点2组合和点2和点1组合一样) int x1=vec[i].first,y1=vec[i].second; //提取出第一个点的横、纵坐标 int x2=vec[j].first,y2=vec[j].second; //提取出第二个点的横、纵坐标 int A=y2-y1,B=x1-x2,C=x2*y1-x1*y2; //见草稿纸代入(x1,y1),(x2,y2)到Ax+By+C=0得到A,B,C int gcdd=__gcd(__gcd(A,B),C); //为了避免同一条直线因为系数的倍数关系而被重复存储//(例如2x+3y+4=0和4x+6y+8=0表示同一条直线),计算A,B,C的最大公约数gcdd,将直线方程系数//进行化简 s.insert({{A/gcdd,B/gcdd},C/gcdd}); //将化简后的直线信息以PIII的形式插入到set容器s中//由于set的自动去重特性,重复的直线不会被重复插入//pair类型的参数用大括号{}括起来,这里是PIII,还存在两个大括号嵌套 }}cout<<s.size()<<endl;return 0;
}
//set去重和map去重的比较:
//1.set只存储单一元素,map存储的是键值对,如果只需要去重并保留元素本身,使用set更合适,如果需要为每一
//个元素关联一个而外的值,则使用map更合适
//2.set的使用更加简洁,因为不需要处理键值对的映射关系第二种方式代码详解：
#include<bits/stdc++.h> //填空题,答案是40257
using namespace std;typedef pair<int,int> PII;
typedef pair<PII,int> PIII;set<PIII> s;vector<PII> vec;int main()
{for(int i=0;i<20;i++){for(int j=0;j<21;j++){vec.push_back({i,j});}}for(int i=0;i<vec.size();i++){for(int j=i+1;j<vec.size();j++){int x1=vec[i].first,y1=vec[i].second;int x2=vec[j].first,y2=vec[j].second;int A=y1-y2,B=x2-x1,C=x1*y2-x2*y1; //草稿纸上有详细推导,看似和直接代入的不一样,实际//就是三个参数都乘了-1,还是表示同一条直线 int gcdd=__gcd(__gcd(A,B),C);s.insert({{A/gcdd,B/gcdd},C/gcdd});}}cout<<s.size()<<endl;return 0;
}