2021年蓝桥杯省赛
题目链接：http://acm.mangata.ltd/p/P1485
考点数学、暴力
视频讲解https://www.bilibili.com/video/BV1BY411J795
思路因为选取的点都是整数坐标的，于是我们最多选取
21
×
20
=
420
21\times 20 = 420
21×20=420 个点，那么对于其中每两个点我们都能选来作为一条直线，但是这样的话可能会存在重复选择一条线，于是我们需要去重处理，那么怎么去重呢？我们知道对于一个直线的标准方程为：
A
x
+
B
y
+
C
=
0
Ax+By+C = 0
Ax+By+C=0 那么也就是说我们只要确定了
A
、
B
、
C
A、B、C
A、B、C 即可，不过这里需要注意这里的
A
、
B
、
C
A、B、C
A、B、C 是需要最简化的，否则就不能达到我们去重的效果，对于三个元素或者多个元素的结构去重，我们可以选择自己写一个结构体，但是我们也可以直接使用 vector ，然后把每个vector 扔进 set 里面即可，那么我们怎么求得
A
、
B
、
C
A、B、C
A、B、C 呢？，大家都知道两点确定直线的方程：
(
y
−
y
1
)
y
1
−
y
2
=
x
−
x
1
x
1
−
x
2
\frac{(y - y_1)}{y_1-y_2} = \frac{x-x_1}{x_1-x_2}
y1−y2(y−y1)=x1−x2x−x1 那么我们稍微等式变换一下就能得到：
(
y
2
−
y
1
)
x
+
(
x
1
−
x
2
)
y
+
(
x
2
y
1
−
x
1
y
2
)
=
0
(y_2 - y_1)x + (x_1-x_2)y + (x_2y_1-x_1y_2) = 0
(y2−y1)x+(x1−x2)y+(x2y1−x1y2)=0
我们和上面一一对应就能得到：
A
=
y
2
−
y
1
、
B
=
x
1
−
x
2
、
C
=
x
2
y
1
−
x
1
y
2
A=y_2 - y_1、B=x_1-x_2、C=x_2y_1-x_1y_2
A=y2−y1、B=x1−x2、C=x2y1−x1y2，那么我们在将三者的公因数都除掉后放入vector中，再丢入set 就完成了一条线的计算，最后我们只需要输出set容器里面的大小即可
#include
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f
const double eps = 0.0000001;
int main()
{
vector Point;
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 20,m = 21;
// cin>>n>>m;
for(int x = 0;x
关注
打赏
![]()
1665836431
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
