Сообщения без ответов | Активные темы
| Автор | Сообщение | ||
|---|---|---|---|
|
zuster |
Заголовок сообщения: Ближайшая точка к началу координат
|
||
|
Здравствуйте.
|
||
| Вернуться к началу |
|
||
 |
Добавлено: 08 май 2023, 14:25 
|
Pirinchily |
Заголовок сообщения: Re: Ближайшая точка к началу координат
|
|
Надо решать задачу : Найти [math]min left( sqrt{x^2+y^2+z^2} right)[/math], при удовлетворения условия [math]z= frac{ aleft( y+1 right) }{ xy+y+1 }[/math]
|
|
| Вернуться к началу |
|
|
|
| За это сообщение пользователю Pirinchily “Спасибо” сказали: zuster |
|
|
| Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
|---|---|---|---|---|
|
Доказать что точка а устранимая особая точка
в форуме Комплексный анализ и Операционное исчисление |
Dr_Zet |
3 |
65 |
19 май 2023, 16:34 |
|
Точка
в форуме Дискуссионные математические проблемы |
VIKTORVIKTOR |
0 |
381 |
20 июн 2017, 10:43 |
|
Точка
в форуме Размышления по поводу и без |
mihmih |
48 |
1242 |
12 сен 2017, 02:08 |
|
Три Плоскости и точка
в форуме Аналитическая геометрия и Векторная алгебра |
Olenka_S |
8 |
601 |
09 май 2015, 15:08 |
|
Точка безубыточности
в форуме Экономика и Финансы |
walker_k |
0 |
304 |
01 мар 2019, 15:44 |
|
Точка и квадрат
в форуме Геометрия |
Morody |
6 |
236 |
26 сен 2020, 10:26 |
|
Точка из P_0 между 0.05 и 0.1
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
KirillSavitsky |
1 |
409 |
23 май 2015, 20:36 |
|
Особая точка и её тип
в форуме Комплексный анализ и Операционное исчисление |
Over77over |
1 |
176 |
24 июл 2018, 21:47 |
|
Точка экстремума
в форуме Начала анализа и Другие разделы школьной математики |
VladGreen |
2 |
283 |
18 мар 2018, 11:45 |
|
Точка в диапазоне
в форуме Геометрия |
Kilovatra |
3 |
136 |
27 авг 2021, 13:28 |
Кто сейчас на конференции |
|
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1 |
| Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Вы можете создать форум бесплатно PHPBB3 на Getbb.Ru, Также возможно сделать готовый форум PHPBB2 на Mybb2.ru
Русская поддержка phpBB
Given a list of points on the 2-D plane and an integer K. The task is to find K closest points to the origin and print them.
Note: The distance between two points on a plane is the Euclidean distance.
Examples:
Input : point = [[3, 3], [5, -1], [-2, 4]], K = 2 Output : [[3, 3], [-2, 4]] Square of Distance of origin from this point is (3, 3) = 18 (5, -1) = 26 (-2, 4) = 20 So the closest two points are [3, 3], [-2, 4]. Input : point = [[1, 3], [-2, 2]], K = 1 Output : [[-2, 2]] Square of Distance of origin from this point is (1, 3) = 10 (-2, 2) = 8 So the closest point to origin is (-2, 2)
Approach: The idea is to calculate the Euclidean distance from the origin for every given point and sort the array according to the Euclidean distance found. Print the first k closest points from the list.
Algorithm :
Consider two points with coordinates as (x1, y1) and (x2, y2) respectively. The Euclidean distance between these two points will be:
√{(x2-x1)2 + (y2-y1)2}
- Sort the points by distance using the Euclidean distance formula.
- Select first K points from the list
- Print the points obtained in any order.
Note:
- In multimap we can directly store the value of {(x2-x1)2 + (y2-y1)2} instead of its square root because of the following property : If sqrt(x) < sqrt(y) the x < y
- Because of this, we have reduced the time complexity (Time complexity of the square root of an integer is O(√ n) )
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
void pClosest(vector<vector<int>> pts, int k)
{
multimap<int, int> mp;
for(int i = 0; i < pts.size(); i++)
{
int x = pts[i][0], y = pts[i][1];
mp.insert({(x * x) + (y * y) , i});
}
for(auto it = mp.begin();
it != mp.end() && k > 0;
it++, k--)
cout << "[" << pts[it->second][0] << ", "
<< pts[it->second][1] << "]" << "n";
}
int main()
{
vector<vector<int>> points = { { 3, 3 },
{ 5, -1 },
{ -2, 4 } };
int K = 2;
pClosest(points, K);
return 0;
}
Java
import java.util.*;
class GFG{
static void pClosest(int [][]pts, int k)
{
int n = pts.length;
int[] distance = new int[n];
for(int i = 0; i < n; i++)
{
int x = pts[i][0], y = pts[i][1];
distance[i] = (x * x) + (y * y);
}
Arrays.sort(distance);
int distk = distance[k - 1];
for(int i = 0; i < n; i++)
{
int x = pts[i][0], y = pts[i][1];
int dist = (x * x) + (y * y);
if (dist <= distk)
System.out.println("[" + x + ", " + y + "]");
}
}
public static void main (String[] args)
{
int points[][] = { { 3, 3 },
{ 5, -1 },
{ -2, 4 } };
int K = 2;
pClosest(points, K);
}
}
Python3
def pClosest(points, K):
points.sort(key = lambda K: K[0]**2 + K[1]**2)
return points[:K]
points = [[3, 3], [5, -1], [-2, 4]]
K = 2
print(pClosest(points, K))
C#
using System;
class GFG{
static void pClosest(int [,]pts,
int k)
{
int n = pts.GetLength(0);
int[] distance = new int[n];
for(int i = 0; i < n; i++)
{
int x = pts[i, 0],
y = pts[i, 1];
distance[i] = (x * x) +
(y * y);
}
Array.Sort(distance);
int distk = distance[k - 1];
for(int i = 0; i < n; i++)
{
int x = pts[i, 0],
y = pts[i, 1];
int dist = (x * x) +
(y * y);
if (dist <= distk)
Console.WriteLine("[" + x +
", " + y + "]");
}
}
public static void Main (string[] args)
{
int [,]points = {{3, 3},
{5, -1},
{-2, 4}};
int K = 2;
pClosest(points, K);
}
}
Javascript
<script>
function pClosest(pts,k)
{
let n = pts.length;
let distance = new Array(n);
for(let i = 0; i < n; i++)
{
let x = pts[i][0], y = pts[i][1];
distance[i] = (x * x) + (y * y);
}
distance.sort(function(a,b){return a-b;});
let distk = distance[k - 1];
for(let i = 0; i < n; i++)
{
let x = pts[i][0], y = pts[i][1];
let dist = (x * x) + (y * y);
if (dist <= distk)
document.write("[" + x + ", " + y + "]<br>");
}
}
let points = [[3, 3], [5, -1], [-2, 4]];
let K = 2;
pClosest(points, K);
</script>
Complexity Analysis:
- Time Complexity: O(n log n).
Time complexity to find the distance from the origin for every point is O(n) and to sort the array is O(n log n) - Space Complexity: O(n).
As we are making an array to store distance from the origin for each point.
Last Updated :
03 Oct, 2022
Like Article
Save Article
Помогите с заданием пожалуйста!
Даны действительные числа x0, y0, x1, y1, x2, y2, x3, y3 . На плоскости заданы точки A(x1, y1), B(x2,y2) и C(x3, y3) . Определить, какая из этих точек является ближайшей к началу координат.
Вот мои попытки, что то не получается.. выводиться только точка С
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
double x0, y0, x1, y1, x2, y2, x3, y3, r1, r2, r3, minR;
string min;
x0 = 0;
y0 = 0;
Console.WriteLine("Точка А");
Console.WriteLine("Введите значение x1");
x1 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Введите значение y1");
y1 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Точка B");
Console.WriteLine("Введите значение x2");
x2 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Введите значение y2");
y2 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Точка C");
Console.WriteLine("Введите значение x3");
x3 = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Введите значение y3");
y3 = Convert.ToDouble(Console.ReadLine());
r1 = Math.Pow((Math.Pow((x0 - x1), 2) + Math.Pow((y0 - y1), 2)), 0.5);
r2 = Math.Pow((Math.Pow((x0 - x2), 2) + Math.Pow((y0 - y2), 2)), 0.5);
r3 = Math.Pow((Math.Pow((x0 - x3), 2) + Math.Pow((y0 - y3), 2)), 0.5);
minR = 0;
min = "0";
if (r1 > minR)
{
min = "A";
}
if (r2 > minR)
{
min = "B";
}
if (r3 > minR)
{
min = "C";
}
if ((r1 == r2) && (r1 == minR))
{
min = "A,B";
}
if ((r2 == r3) && (r2 == minR))
{
min = "B,C";
}
if ((r1 == r3) && (r1 == minR))
{
min = "A,C";
}
if ((r1 == r2) && (r2 == r3) && (r1 == minR))
{
min = "A,B,C";
}
Console.WriteLine("Ответ:");
Console.WriteLine("Наименьшее расстояние до начала координат от точки " + min);
Console.ReadKey();
}
}
}
Visual studio c# 2010 express
Код к задаче: «Найти ближайшую точку к началу координат»
Найти ближайшую точку в системе координат?
Есть таблица в БД с координатами в формате 55.888755,37.430337 и сами заданные координаты в таком же формате. Как найти ближайшие координаты к заданным координатам? Интересен сам алгоритм, а не код конечно=)
-
Вопрос заданболее трёх лет назад
-
7757 просмотров
1) Берем массив с точками
2) Берем заданную точку
3) Находим расстояние между точками
4) ???
5) Profit!!1
PS
По ссылке формула для координат на плоскости. Если нужно с учетом искривления земли -> гугл.
Пригласить эксперта
Напишу алгоритм “в лоб”.
Пройтись по каждой точке в БД – найти расстояние между двумя точками (между заданной точкой и точкой в базе);
Среди этих значений найти минимальное.
Если точек много (очень много), то поиск можно сузить применяя сравнение по hashcode.
-
Показать ещё
Загружается…
23 мая 2023, в 20:04
7000 руб./за проект
23 мая 2023, в 19:34
10000 руб./за проект
23 мая 2023, в 19:03
750 руб./за проект
