当前位置:网站首页>[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;
}
边栏推荐
- Kept VRRP script, preemptive delay, VIP unicast details
- AI benchmark V5 ranking
- 01项目需求分析 (点餐系统)
- 基于apache-jena的知识问答
- Summary of numpy installation problems
- How to build a new project for keil5mdk (with super detailed drawings)
- ES6 promise object
- Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
- neo4j安装教程
- Error reporting solution - io UnsupportedOperation: can‘t do nonzero end-relative seeks
猜你喜欢
neo4j安装教程
MTCNN人脸检测
Valentine's Day flirting with girls to force a small way, one can learn
[蓝桥杯2017初赛]方格分割
Nanny level problem setting tutorial
Double to int precision loss
In the era of DFI dividends, can TGP become a new benchmark for future DFI?
Software testing and quality learning notes 3 -- white box testing
Learn winpwn (3) -- sEH from scratch
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
随机推荐
Did you forget to register or load this tag
JDBC原理
Valentine's Day flirting with girls to force a small way, one can learn
Database advanced learning notes -- SQL statement
Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
How to build a new project for keil5mdk (with super detailed drawings)
AI benchmark V5 ranking
Record a problem of raspberry pie DNS resolution failure
Attention apply personal understanding to images
JDBC原理
How to set up voice recognition on the computer with shortcut keys
QT creator uses Valgrind code analysis tool
Software I2C based on Hal Library
QT creator specifies dependencies
In the era of DFI dividends, can TGP become a new benchmark for future DFI?
AcWing 1298. Solution to Cao Chong's pig raising problem
Error reporting solution - io UnsupportedOperation: can‘t do nonzero end-relative seeks
Django运行报错:Error loading MySQLdb module解决方法
[number theory] divisor
Why can't I use the @test annotation after introducing JUnit