当前位置:网站首页>[蓝桥杯2020初赛] 平面切分
[蓝桥杯2020初赛] 平面切分
2022-07-06 09:14:00 【%xiao Q】
题目
题目描述
平面上有N 条直线,其中第i 条直线是y = Ai * x + Bi。
请计算这些直线将平面分成了几个部分。
输入格式
第一行包含一个整数N。
以下N 行,每行包含两个整数Ai, Bi。
对于50% 的评测用例,1 ≤ N ≤ 4, -10 ≤ Ai, Bi ≤ 10。
对于所有评测用例,1 ≤ N ≤ 1000, -100000 ≤ Ai, Bi ≤ 100000。
输出格式
一个整数代表答案。
输入样例 复制
3
1 1
2 2
3 3
输出样例 复制
6
分析
这道题目首先我们得知道一个数学小常识:在同一个平面内,如果添加一条直线,与平面所有的直线不相交,则会增加一个平面,如果与这个平面内的一条直线相交并且产生不同的位置的交点,那么就会额外增加一个平面。
那么我们在做题的过程中,只需判断是否时重边,计算新增加的直线与前面的直线有多少个不同的交点,重边非常的好判断,直接用一个数组标记一下即可,计算交点我们也可以用set(可以自动去重)。
参考代码
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 1010;
typedef pair<double, double> PDD;
bool st[N]; //用来标记重边,防止重复计算交点
double a[N][2];
int main()
{
int n;
cin >> n;
int ans = 1; // 一开始有一个平面
rep(i, 1, n)
{
cin >> a[i][0] >> a[i][1];
set<PDD> point; // 计算该直线与平面内的直线的不同交点的个数
rep(j, 1, i - 1)
{
if(st[j]) continue;
if(a[i][0] == a[j][0])
{
if(a[i][1] == a[j][1])
{
st[i] = true;
break;
}
else continue;
}
double x = (a[i][1] - a[j][1]) / (a[j][0] - a[i][0]);
double y = a[i][0] * x + a[i][1];
point.insert({
x, y});
}
if(!st[i]) ans += point.size() + 1;
}
cout << ans << endl;
return 0;
}
边栏推荐
- MySQL完全卸载(Windows、Mac、Linux)
- QT creator support platform
- 记某公司面试算法题:查找一个有序数组某个数字出现的次数
- One click extraction of tables in PDF
- Number game
- 软件测试-面试题分享
- Why can't I use the @test annotation after introducing JUnit
- [recommended by bloggers] asp Net WebService background data API JSON (with source code)
- Record a problem of raspberry pie DNS resolution failure
- Remember a company interview question: merge ordered arrays
猜你喜欢
windows下同时安装mysql5.5和mysql8.0
【博主推荐】asp.net WebService 后台数据API JSON(附源码)
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
MySQL master-slave replication, read-write separation
Asp access Shaoxing tourism graduation design website
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
机器学习笔记-Week02-卷积神经网络
La table d'exportation Navicat génère un fichier PDM
Other new features of mysql18-mysql8
MySQL主從複制、讀寫分離
随机推荐
CSDN Q & a tag skill tree (V) -- cloud native skill tree
Rhcsa certification exam exercise (configured on the first host)
安全测试涉及的测试对象
Leetcode 461 Hamming distance
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
【博主推荐】C#生成好看的二维码(附源码)
01 project demand analysis (ordering system)
Learning question 1:127.0.0.1 refused our visit
There are three iPhone se 2022 models in the Eurasian Economic Commission database
[C language foundation] 04 judgment and circulation
Did you forget to register or load this tag
Julia 1.6 1.7 common problem solving
Why can't I use the @test annotation after introducing JUnit
QT creator uses Valgrind code analysis tool
Machine learning -- census data analysis
Request object and response object analysis
A trip to Macao - > see the world from a non line city to Macao
QT creator test
Remember a company interview question: merge ordered arrays
Error reporting solution - io UnsupportedOperation: can‘t do nonzero end-relative seeks