手机网站模板 商城,织梦 更换网站图标,宁波seo推荐推广平台,html代码按钮问题描述 平面上有 N条直线#xff0c;其中第 i条直线是 y Ai*x B。
请计算这些直线将平面分成了几个部分。
输入格式 第一行包含一个整数N。
以下N行#xff0c;每行包含两个整数 Ai, Bi。
输出格式 一个整数代表答案。
样例输入
3
1 1
2 2
3 3样例输出
6基本思路 …问题描述 平面上有 N条直线其中第 i条直线是 y Ai*x B。
请计算这些直线将平面分成了几个部分。
输入格式 第一行包含一个整数N。
以下N行每行包含两个整数 Ai, Bi。
输出格式 一个整数代表答案。
样例输入
3
1 1
2 2
3 3样例输出
6基本思路 首先通过set容器对输入的数据进行去重根据“每增加一条直线对平面数增加的贡献值是其与先前直线的交点数不包括与已有交点重合的点1 ”的结论进行累加最后输出结果即可具体步骤见代码注释~。
AC代码
#includebits/stdc.h
using namespace std;
const int N 1005;int main()
{int n;scanf(%d, n);int a, b;long double A[N], B[N];pairlong double, long double p; setpairlong double, long double s; //利用set自动去重功能筛选掉重边 for(int i 0; i n; i){scanf(%d %d, a, b);p.first a;p.second b;s.insert(p);}int i 0; //将去重后的直线数据放回A,B数组 for(setpairlong double, long double ::iterator it s.begin(); it ! s.end(); it, i){A[i] it - first;B[i] it - second;}long long ans 2; //初始情况当只有一条直线时有两个平面 for(int i 1; i s.size(); i) //从下标1开始也就是第二条直线 {setpairlong double, long double pos; //记录第i条直线与先前的交点 for(int j i-1; j 0; j--){int a1 A[i], b1 B[i];int a2 A[j], b2 B[j];if(a1 a2) //遇到平行线无交点跳出 continue; p.first 1.0*(b2-b1)/(a1-a2);p.second 1.0*a1*((b2-b1)/(a1-a2)) b1;pos.insert(p); }ans pos.size() 1; //根据结论每增加一条直线对平面数的贡献值是其与先前直线的交点数不重合1 } printf(%d\n, ans);return 0;
}
