平面中相交的线段将与水平线相交多少?什么是找到这个最有效的方法 [英] how many line segments will intersect in a plane will intersect with a horizontal line ? what will be the most effective way to find this

问题描述

我正在尝试解决此Cyber​​chef挑战:

在一个平面上给您N个点(编号1到N)；对于每个有效i，第i个点为Pi =(i，Ai).它们之间有N-1个线段(编号1到N-1).对于每个有效的i，通过连接点Pi和Pi + 1形成第i条线段.

You are given N points in a plane (numbered 1 through N); for each valid i, the i-th point is Pi=(i,Ai). There are N−1 line segments between them (numbered 1 through N−1); for each valid i, the i-th line segment is formed by connecting the points Pi and Pi+1.

您将获得Q条水平线段.每个查询水平线段由两个点表示，从点(x1，y)到点(x2，y)(在该点停止并且不再传播).对于每个水平线段"，您必须从与之相撞的那些线段(N-1个线段)中找到线段的数量.

You are given Q horizontal line segments . Each query horizontal line segment is denoted by two points, from a point (x1,y) to a point (x2,y) (where it stops and does not propagate further). For Every Horizontal line segment, you have to find the number of line segments from those (N-1 line segments) it collides with on the way.

这是其中的问题:

• 2< = N&=; 100000
• 1< = Q< = 100000

有人可以教我哪种方法在时间复杂度方面是最好和最有效的吗?

Can anyone teach me what approach will be best and most effective in terms of time complexity?

推荐答案

我使用k-d树来解决此问题.也不要问正在挑战的问题.

I used k-d tree to solve this problem. Also dont ask questions that are on-going challenges.

这篇关于平面中相交的线段将与水平线相交多少?什么是找到这个最有效的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！