宁波工程学院2020新生校赛C

宁波工程学院2020新生校赛C

链接：
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小梁旅途的第一站，来到了杰尼龟兄弟的栖息地，正巧赶上杰尼龟兄弟们在举行神奇的数学游戏，它们把广阔的湖面当做二维坐标系，他们分别站在某一点向某一方向发射高压水枪，这些高压水枪相互穿透，构成了多个交点。
现在小梁通过建模，把每道高压水枪抽象成了y = k*x+b
​
的直线，现在她想知道那些高压水枪能构成多少个不同的交点。
输入描述:
第一行输入一个整数n(1≤n≤100)，表示杰尼龟兄弟的数量
下面n行每行包括两个整数，k和b，和直线方程意义相同。
在64位整形的范围内
输出描述:
如果不存在交点输出"No Fire Point." (不包括引号)

否则输出一个整数表示不同交点的个数。

示例1
输入
2
1 0
-1 2
输出
1

题目大意：

输入一个n表示有n条线，然后接下来的n行，给出每条线的斜截式方程，求这些线的交点数。

解题思路：

计算几何+思维，给出了一些斜截式方程，因为n只有100，可以枚举所有两两一组可能的情况，并求一下交点，把交点存入集合set（去重），最后输出set.size()。求交点：

• y = k1*x+b1
• y = k2*x+b2
  联立：k1x+b1 = k2x+b2
  整理：x(k1-k2)=(b2-b1)

则 x= (b2-b1)/(k1-k2)
求y把x带入即可。
注意下判断k1 == k2 ，如果等于k2则continue，因为斜率相等没有交点
AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<double ,double > pdd;
set<pdd >se;
ll k[110],b[110];
int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>k[i]>>b[i];for(int i=0;i<n-1;i++)//两两枚举for(int j=i+1;j<n;j++){if(k[i]==k[j])continue;double ex = double(b[j]-b[i])/(k[i]-k[j]);//交点double ey = double(k[i])*ex+b[i];pdd t;//借助pair存入sett.first=ex;t.second=ey;se.insert(t);}if(!se.size())cout<<"No Fire Point."<<endl;elsecout<<se.size()<<endl;//system("pause");return 0;
}