current position：Home>leetcode 1610. Maximum Number of Visible Points（python）
leetcode 1610. Maximum Number of Visible Points（python）
20220201 06:23:56 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 23 God , Check out the activity details ：2021 One last more challenge 」
describe
You are given an array points, an integer angle, and your location, where location = [pos_{x}, pos_{y}] and points[i] = [x_{i}, y_{i}] both denote integral coordinates on the XY plane.
Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, pos_{x} and pos_{y} cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d  angle/2, d + angle/2].
You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.
There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.
Return the maximum number of points you can see.
Example 1:
Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Copy code
Example 2:
Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
Output: 4
Explanation: All points can be made visible in your field of view, including the one at your location.
Copy code
Example 3:
Input: points = [[1,0],[2,1]], angle = 13, location = [1,1]
Output: 1
Explanation: You can only see one of the two points, as shown above.
Copy code
Note:
 1 <= points.length <= 10^5
 points[i].length == 2
 location.length == 2
 0 <= angle < 360
 0 <= pos_{x}, pos_{y}, x_{i}, y_{i} <= 100
analysis
According to the meaning , Given a list points 、 An integer angle And your location , among location = [pos_{x}, pos_{y}] and points[i] = [x_{i}, y_{i}] All means XY Integral coordinates on the plane .
first , Stand in your position and face directly to the East . You can't move from your position , But you can rotate . let me put it another way ,pos_{x} and pos_{y} Can't change . The field of view in degrees consists of angle Express , Determines the width that can be seen from any given line of sight . Give Way d Indicates the number of degrees you rotate counterclockwise . then , Your vision is the angle [d  angle/2, d + angle/2] The scope of .
If for each point , From this point 、 Your position and the angle from your position directly to the East are in your view , You can see a collection of points . There can be multiple points on a coordinate . Your location may be a little , No matter how you rotate , You can always see these points . Points do not interfere with your view of other points . Return the maximum number of points you can see .
In fact, this question is relatively simple after reading , The general idea is to location As the origin , And then calculate points The angle between each point in the and the origin , It's all recorded angles in , Then use the sliding window idea to find angle The point with the most points in the range . There are two points in the title that need special attention ：
 The first is to calculate the included angle , The scope of attention is [0, 2*pi] , But maybe in 0 There may be an angle in line with the meaning of the topic up and down around the degree , So we need to angles Then expand each element and add 2*pi Value , Can be said [2*pi, 4*pi] The scope of the
 The second is the precision of decimals , Must be considered in place , After all, the computer is a floating point number when calculating the included angle , If the accuracy is not enough, there may be errors in finding points
 The third is that some points are at the origin , These points can always be seen , Just add it directly to the result
answer
class Solution(object):
def visiblePoints(self, points, angle, location):
"""
:type points: List[List[int]]
:type angle: int
:type location: List[int]
:rtype: int
"""
angles = []
pi = 3.1415926
origin = 0
for x, y in points:
dx = x  location[0]
dy = y  location[1]
if dx == 0 and dy == 0:
origin += 1
continue
alpha = atan2(dy, dx) + pi
angles.append(alpha)
angles.sort()
N = len(angles)
for i in range(N):
angles.append(angles[i] + 2 * pi)
result = j = 0
for i in range(2*N):
while j < 2 * N and angles[j]  angles[i] <= angle * 1.0 * pi / 180 + 0.0000001:
j += 1
result = max(result, j  i)
return result + origin
Copy code
Running results
Runtime: 2204 ms, faster than 43.70% of Python online submissions for Maximum Number of Visible Points.
Memory Usage: 56.3 MB, less than 36.97% of Python online submissions for Maximum Number of Visible Points.
Copy code
Original link ：leetcode.com/problems/ma…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202010623540138.html
The sidebar is recommended
 Django paging (II)
 Concurrent. For Python concurrent programming Futures or multiprocessing?
 Programmers over the age of 25 can't know a few Chinese herbal medicines. Python crawler lessons 99
 Python crawler from introduction to pit full series of tutorials (detailed tutorial + various practical combat)
 The second bullet of class in Python
 Python object oriented programming 03: class inheritance and its derived terms
 How IOS developers learn Python Programming 13  function 4
 Python crawler from introduction to mastery (VI) form and crawler login
 Python crawler from entry to mastery (V) challenges of dynamic web pages
 Deeply understand pandas to read excel, TXT, CSV files and other commands
guess what you like

Daily python, Chapter 18, class

"I just want to collect some plain photos in Python for machine learning," he said. "I believe you a ghost!"

Django view

Python implements filtering emoticons in text

When winter comes, python chooses a coat with temperament for mom! Otherwise, there's really no way to start!

Python crawler  get fund change information

Highlight actor using Python VTK

Python crawler actual combat: crawling southern weekend news articles

leetcode 406. Queue Reconstruction by Height（python）

leetcode 1043. Partition Array for Maximum Sum （python）
Random recommended
 Python * * packaging and unpacking details
 Python realizes weather query function
 Python from 0 to 1 (day 12)  Python data application 2 (STR function)
 Python from 0 to 1 (day 13)  Python data application 3
 Numpy common operations of Python data analysis series Chapter 8
 How to implement mockserver [Python version]
 Van * Python! Write an article and publish the script on multiple platforms
 Python data analysis  file reading
 Python data De duplication and missing value processing
 Python office automation  play with browser
 Python series tutorial 127  Reference vs copy
 Control flow in Python: break and continue
 Teach you how to extract tables in PDF with Python
 leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal（python）
 leetcode 1338. Reduce Array Size to The Half（python）
 Object oriented and exception handling in Python
 How to configure load balancing for Django service
 How to embed Python in go
 Python Matplotlib drawing graphics
 Python objectoriented programming 05: concluding summary of classes and objects
 Python from 0 to 1 (day 14)  Python conditional judgment 1
 Several very interesting modules in Python
 How IOS developers learn Python Programming 15  object oriented programming 1
 Daily python, Chapter 20, exception handling
 Understand the basis of Python collaboration in a few minutes
 [centos7] how to install and use Python under Linux
 leetcode 1130. Minimum Cost Tree From Leaf Values（python）
 leetcode 1433. Check If a String Can Break Another String（python）
 Python Matplotlib drawing 3D graphics
 Talk about deep and shallow copying in Python
 Python crawler series  network requests
 Python thread 01 understanding thread
 Analysis of earthquake distribution in the past 10 years with Python~
 You need to master these before learning Python crawlers
 After the old friend (R & D post) was laid off, I wanted to join the snack bar. I collected some data in Python. It's more or less a intention
 Python uses redis
 Python crawler  ETF fund acquisition
 Detailed tutorial on Python operation Tencent object storage (COS)
 [Python] comparison of list, tuple, array and bidirectional queue methods
 Go Python 3 usage and pit Prevention Guide