当前位置:网站首页>[Bluebridge cup 2020 preliminary] horizontal segmentation
[Bluebridge cup 2020 preliminary] horizontal segmentation
2022-07-06 11:26:00 【%xiao Q】
subject
Title Description
There is... On the plane N A straight line , Among them the first i This straight line is y = Ai * x + Bi.
Please calculate these lines to divide the plane into several parts .
Input format
The first line contains an integer N.
following N That's ok , Each line contains two integers Ai, Bi.
about 50% The evaluation case of ,1 ≤ N ≤ 4, -10 ≤ Ai, Bi ≤ 10.
For all profiling use cases ,1 ≤ N ≤ 1000, -100000 ≤ Ai, Bi ≤ 100000.
Output format
An integer represents the answer .
sample input Copy
3
1 1
2 2
3 3
sample output Copy
6
analysis
First of all, we need to know a little common sense of Mathematics : In the same plane , If you add a line , It does not intersect all lines in the plane , Then a plane will be added , If it intersects with a straight line in this plane and produces intersections at different positions , Then an additional plane will be added .
Then we are in the process of making questions , Just judge whether to repeat the edge , Calculate the number of different intersections between the newly added line and the previous line , The heavy side is very good judgment , Just mark it with an array , We can also use set( It can automatically remove the weight ).
Reference code
#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]; // Used to mark heavy edges , Prevent double calculation of intersections
double a[N][2];
int main()
{
int n;
cin >> n;
int ans = 1; // At the beginning, there is a plane
rep(i, 1, n)
{
cin >> a[i][0] >> a[i][1];
set<PDD> point; // Calculate the number of different intersections between the line and the line in the plane
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;
}
边栏推荐
- Introduction and use of automatic machine learning framework (flaml, H2O)
- Dotnet replaces asp Net core's underlying communication is the IPC Library of named pipes
- 误删Path变量解决
- AI benchmark V5 ranking
- Base de données Advanced Learning Notes - - SQL statements
- Why can't I use the @test annotation after introducing JUnit
- Integration test practice (1) theoretical basis
- QT creator design user interface
- Picture coloring project - deoldify
- [free setup] asp Net online course selection system design and Implementation (source code +lunwen)
猜你喜欢
Data dictionary in C #
Install mongdb tutorial and redis tutorial under Windows
Use dapr to shorten software development cycle and improve production efficiency
软件测试与质量学习笔记3--白盒测试
Machine learning notes week02 convolutional neural network
基于apache-jena的知识问答
安装numpy问题总结
Introduction and use of automatic machine learning framework (flaml, H2O)
Case analysis of data inconsistency caused by Pt OSC table change
Face recognition_ recognition
随机推荐
Learn winpwn (3) -- sEH from scratch
Solve the problem of installing failed building wheel for pilot
Software testing and quality learning notes 3 -- white box testing
Asp access Shaoxing tourism graduation design website
Case analysis of data inconsistency caused by Pt OSC table change
Nanny level problem setting tutorial
02 staff information management after the actual project
学习问题1:127.0.0.1拒绝了我们的访问
QT creator runs the Valgrind tool on external applications
neo4j安装教程
Vs2019 first MFC Application
Data dictionary in C #
数数字游戏
Did you forget to register or load this tag 报错解决方法
Did you forget to register or load this tag
Kept VRRP script, preemptive delay, VIP unicast details
JDBC原理
Why can't I use the @test annotation after introducing JUnit
Punctual atom stm32f103zet6 download serial port pin
double转int精度丢失问题