温江区规划建设局网站,网站做图分辨率是多少,免费黄页网站,福清市住房城乡建设局网站目录 题目#xff1a;
题目描述#xff1a;
题目链接#xff1a;
思路#xff1a;
核心思路#xff1a;
两点确定一条直线#xff1a;
思路详解#xff1a;
代码#xff1a;
第一种方式代码详解#xff1a;
第二种方式代码详解#xff1a; 题目#xff1a;…目录 题目
题目描述
题目链接
思路
核心思路
两点确定一条直线
思路详解
代码
第一种方式代码详解
第二种方式代码详解 题目
题目描述 题目链接
直线 - 蓝桥云课
思路
核心思路
枚举set去重
两点确定一条直线
第一种推导参数的方式是直接代入两点坐标到一般式中求参数。下图展示了推导过程 第二种推导参数的方式是通过两点式方程求参数。下图展示了推导过程 思路详解
用pairint,int类型来存储两个值即在枚举的时候表示平面直角坐标系中的点。再用pairPII,int类型来存储三个值PII来表示直线的前两个参数A和Bint表示直线的最后一个参数C。定义一个vector容器vec,用于存储给定平面上的所有整点的坐标,元素类型是PII定义一个set容器s,用于存储不同的直线,set容器会自动对元素进行去重,这里的元素类型是PIII,即每一条直线用PIII来表示。然后就是从vec中提取出两个点的横纵坐标并计算得到直线参数ABC。这里注意为了避免同一条直线因为系数的倍数关系而被重复存储我们要利用__gcd()最小公倍数函数对直线方程系数进行化简。将化简后的直线信息以PIII的形式插入到set容器s中由于set会自动去重所以最后的结果就是set容器的大小
代码
第一种方式代码详解
#includebits/stdc.h //填空题,答案是40257
using namespace std; //思路主要就是枚举和去重,存储三个参数用pair来表示,去重用set集合 typedef pairint,int PII; //将pairint,int类型重命名为PII,方便后续代码书写,pair用于存储两个值,//这里用来表示平面直角坐标系中的点,横坐标和纵坐标都是int类型
typedef pairPII,int PIII; //将pairPII,int类型重命名为PIII,方便后续代码书写,这里PII表示直线的//一般式方程的前两个参数A和B,int表示一般式方程的最后一个参数C setPIII s; //定义一个set容器s,用于存储不同的直线,set容器会自动对元素进行去重,这里的元素类型是//PIII,即每一条直线用PIII来表示 vectorPII vec; //定义一个vector容器vec,用于存储给定平面上的所有整点的坐标,元素类型是PII int main()
{for(int i0;i20;i) //由题遍历横坐标0i20,纵坐标0j21的所有整点,将每个点的坐标(i,j)以 { //PII的形式存入vec容器中 for(int j0;j21;j){vec.push_back({i,j});}}for(int i0;ivec.size();i) //外层遍历vec中的每一个点(索引为i) {for(int ji1;jvec.size();j) //内层循环从i1开始遍历(索引为j),这样可以保证每两个点只 { //合一次(避免重复计算直线,点1和点2组合和点2和点1组合一样) int x1vec[i].first,y1vec[i].second; //提取出第一个点的横、纵坐标 int x2vec[j].first,y2vec[j].second; //提取出第二个点的横、纵坐标 int Ay2-y1,Bx1-x2,Cx2*y1-x1*y2; //见草稿纸代入(x1,y1),(x2,y2)到AxByC0得到A,B,C int gcdd__gcd(__gcd(A,B),C); //为了避免同一条直线因为系数的倍数关系而被重复存储//(例如2x3y40和4x6y80表示同一条直线),计算A,B,C的最大公约数gcdd,将直线方程系数//进行化简 s.insert({{A/gcdd,B/gcdd},C/gcdd}); //将化简后的直线信息以PIII的形式插入到set容器s中//由于set的自动去重特性,重复的直线不会被重复插入//pair类型的参数用大括号{}括起来,这里是PIII,还存在两个大括号嵌套 }}couts.size()endl;return 0;
}
//set去重和map去重的比较:
//1.set只存储单一元素,map存储的是键值对,如果只需要去重并保留元素本身,使用set更合适,如果需要为每一
//个元素关联一个而外的值,则使用map更合适
//2.set的使用更加简洁,因为不需要处理键值对的映射关系
第二种方式代码详解
#includebits/stdc.h //填空题,答案是40257
using namespace std;typedef pairint,int PII;
typedef pairPII,int PIII;setPIII s;vectorPII vec;int main()
{for(int i0;i20;i){for(int j0;j21;j){vec.push_back({i,j});}}for(int i0;ivec.size();i){for(int ji1;jvec.size();j){int x1vec[i].first,y1vec[i].second;int x2vec[j].first,y2vec[j].second;int Ay1-y2,Bx2-x1,Cx1*y2-x2*y1; //草稿纸上有详细推导,看似和直接代入的不一样,实际//就是三个参数都乘了-1,还是表示同一条直线 int gcdd__gcd(__gcd(A,B),C);s.insert({{A/gcdd,B/gcdd},C/gcdd});}}couts.size()endl;return 0;
}
