Форум программистов
Реклама:
Контент-фильтр ИКС для учебных заведений.
Готовый набор правил для школ, фильтрация по спискам Роскомнадзора и Минюста. Соответствует ФЗ №436 и №139.
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > .NET > C# (си шарп)
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы
Старый 09.01.2017, 12:31   #1
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию Выделить из заданных точек вершины квадрата, содержащего максимальное число заданных точек

Здравствуйте, нужна помощь.
Условие: На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек.
ПРИМЕЧАНИЕ: предполагается, что точки, расположенные на сторонах квадрата, принадлежат ему.
Kef1r вне форума   Ответить с цитированием
Старый 09.01.2017, 12:49   #2
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 22,096
Репутация: 5003
По умолчанию

В чём именно нужна помощь?

ваша задача разбивается на подзадачи.
1-я. описание и ввод исходных данных (в массив, например)
2-я. перебор всех точек по 4-ре. (я бы сделал просто вложенными циклами)
3-я. проверка, образуют ли точки квадрат
4-я. функция проверки, попадает ли заданная точка в квадрат.
думаю, что Вы легко найдёте подходящий алгоритм. Можно, например, подсчитать площади треугольников, которая образует данная точка с вершинами квадрата, сложить их, если площадь совпадает с площадью квадрата, то точка принадлежит квадрату, иначе - не принадлежит. для ускорения можно выделить отдельный случай, когда точка лежит на стороне квадрата.
перебор в цикле всех точек и проверка с помощью функции принадлежности, попадает точка в квадрат или нет.
5-я. поиск максимального значения для количества точек, попавших в квадрат
ну и вывод результата, конечно.

учтите, что, точки Вам придётся подбирать искусственно, боюсь, что рандомные точки вообще не позволят на них нарисовать ни одного квадрата.
Я бы нарисовал несколько квадратов, их координаты забил в программу + добавил K точек со случайными координатами.

Последний раз редактировалось Serge_Bliznykov; 09.01.2017 в 12:51.
Serge_Bliznykov вне форума   Ответить с цитированием
Старый 09.01.2017, 13:34   #3
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию

У меня есть код на паскале, но программа не верно считает количество точек.
Мне бы сначала разобраться почему, а потом переделать на C#.
Код программы на паскаль:
Код:

{В исходном множестве поочередно перебираются все пары точек.}
{Предполагая, что отрезок, соединяющий эти точки, является ребром}
{квадрата строим квадрат и смотрим, все ли его вершины имеются в}
{исходном множестве. Если все, то определяем, сколько точек из}
{исходного множества лежит внутри этого квадрата. Если это число}
{превосходит старый рекорд то запоминаем найденный квадрат.}
{ }
{$A-,B-,D-,E+,F-,I+,L-,N-,O-,R-,S-,V-}
{$M 65520,0,655360}
uses crt;
const
maxn = 100;{ Максимальное число точек }
type
 xy = record x,y : real end; { Тип для записи координат точек }
var
 m : array[1..maxn] of xy; { Координаты точек множества }
 i,j,g,k,n,p : word; { вспомогательные переменные  }
 num : word; { для записи числа точек в текущем квадрате }
 rec : word; { для записи числа точек в лучшем квадрате }
 a1,b1,c1 : real; { вспомогательные переменные  }
 r,c : array[1..5] of xy;{ для записи вершин квадратов }
 f1,f2 : boolean;
 o : array[1..4] of shortint;
Function sign(a : real) : shortint;{ Функция signum }
begin
 if a<0 then sign:=-1
 else if a>0 then sign:=1
 else sign:=0
end;
{ нахождение коэффициентов прямой, 
проходящей через точки x1,y1 и x2,y2 }
procedure getabc(x1,y1,x2,y2:real; var a,b,c:real);
begin
a:=y2-y1; b:=x1-x2; c:=-(a*x1+b*y1)
end;
begin
 write('Введите число точек...'); readln(n);
 for i:=1 to n do
 begin
 write('Введите координаты ',i,'-ой точки...');
 readln(m[i].x,m[i].y); end;
 rec:=0;{ Обнуление рекорда }
for i:=1 to n do
 { Перебор всех квадратов, для которых отрезок m[i]-m[j] }
 for j:=1 to n do { является ребром }
 if i<>j then
 begin
c[1]:=m[i]; c[2]:=m[j];
 { Определение вершин квадрата } 
 c[3].x:=c[2].x+(c[1].y-c[2].y);
 c[3].y:=c[2].y+(c[2].x-c[1].x);
 c[4].x:=c[1].x+(c[1].y-c[2].y);
 c[4].y:=c[1].y+(c[2].x-c[1].x);
 c[5]:=c[1];
 num:=0;
{ Проверка на наличие всех вершин квадрата 
в исходном множестве точек }
f1:=false; f2:=false; 
for g:=1 to n do 
if (m[g].x=c[3].x) and (m[g].y=c[3].y) then f1:=true; 
for g:=1 to n do 
if (m[g].x=c[4].x) and (m[g].y=c[4].y) then f2:=true; 
 if (c[1].x=c[2].x) and (c[1].y=c[2].y) then f1:=false;
if f1 and f2 then 
{Если все вершины квадрата есть в исходном множестве}
for k:=1 to n do { то определяем число точек в квадрате}
 begin
 for g:=1 to 4 do
 begin
getabc(c[g].x,c[g].y,c[g+1].x,c[g+1].y,a1,b1,c1);
 o[g]:=sign(a1*m[k].x+b1*m[k].y+c1);
 end;
 if ((o[1]=o[2]) and (o[2]=o[3]) and (o[3]=o[4])) or
((o[1]=o[2]) and (o[2]=o[3]) and (o[4]=0)) or 
((o[1]=o[2]) and (o[2]=o[4]) and (o[3]=0)) or 
((o[1]=o[3]) and (o[3]=o[4]) and (o[2]=0)) or 
((o[2]=o[3]) and (o[3]=o[4]) and (o[1]=0)) or 
((m[k].x=c[1].x) and (m[k].y=c[1].y)) or 
((m[k].x=c[2].x) and (m[k].y=c[2].y)) or ((m[k].x=c[3].x)
 and (m[k].y=c[3].y)) or ((m[k].x=c[4].x) 
 and (m[k].y=c[4].y)) then inc(num);
 end;
 if rec<num then begin r:=c; rec:=num end;
 end;
 if rec=0 then { Не найдено ни одного квадрата }
 begin
 writeln('Не найдено ни одного квадрата.'); halt
 end;
 { Вывод результатов }
 write('Лучший квадрат : ');
for i:=1 to 3 do write('(',r[i].x:2:2,',',r[i].y:2:2,')-'); 
writeln('(',r[4].x:2:2,',', r[4].y:2:2,').'); 
writeln('В нем находится ',rec,' точек.');
end.

Скриншот запущенной программы ниже.
По идее точек входящих в этот квадрат 7, а пишет что 8.
Изображения
Тип файла: png Безымянный1.png (44.3 Кб, 35 просмотров)
Kef1r вне форума   Ответить с цитированием
Старый 09.01.2017, 14:03   #4
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 16,332
Репутация: 5824
По умолчанию

Цитата:
По идее точек входящих в этот квадрат 7, а пишет что 8.
Пишет правильно. Идея видимо не правильная ))
__________________
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума   Ответить с цитированием
Старый 09.01.2017, 14:10   #5
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Пишет правильно. Идея видимо не правильная ))
Спасибо, уже заметил.
Kef1r вне форума   Ответить с цитированием
Старый 09.01.2017, 18:02   #6
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию

Кто-то может помочь код с паскаля, который выше переделать под C#? А то я застопился в самом начале, не знаю как мне паскальный тип record переделать под C#.
Kef1r вне форума   Ответить с цитированием
Старый 12.01.2017, 13:29   #7
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию

Сделал для 4-х точек, как делать дальше не знаю. Нужен ваш хелп.

Код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine("Сколько будет точек?");
          int  n = Convert.ToInt32(Console.ReadLine());
            int[] dotX = new int[n];
            int[] dotY = new int[n];
            int[] l = new int[6];
            double d1, d2, d3, di1, di2;
            Console.WriteLine("Введите координаты точек");
            for (int i = 0; i < n; i++)
            {
                Console.Write("X{0} = ", i + 1);
                dotX[i] = Convert.ToInt32(Console.ReadLine());
                Console.Write("Y{0} = ", i + 1);
                dotY[i] = Convert.ToInt32(Console.ReadLine());

            }
            for (int i = 0; i < 1; i++)
            {

                    d1 = Math.Sqrt(Math.Pow(dotX[i + 1] - dotX[i], 2) + Math.Pow(dotY[i + 1] - dotY[i], 2));
                    d2 = Math.Sqrt(Math.Pow(dotX[i + 2] - dotX[i + 1], 2) + Math.Pow(dotY[i + 2] - dotY[i + 1], 2));
                    d3 = Math.Sqrt(Math.Pow(dotX[i + 3] - dotX[i + 2], 2) + Math.Pow(dotY[i + 3] - dotY[i + 2], 2));

                di1 = Math.Sqrt(Math.Pow(dotX[i + 2] - dotX[i], 2) + Math.Pow(dotY[i + 2] - dotY[i], 2));
                di2 = Math.Sqrt(Math.Pow(dotX[i + 3] - dotX[i + 1], 2) + Math.Pow(dotY[i + 3] - dotY[i + 1], 2));



            if (Math.Abs(d1 - d2) < 0.0001 && Math.Abs(d2 - d3) < 0.0001 && Math.Abs(di1 - di2) < 0.0001)
            {
                Console.WriteLine("Квадрат");
            }
            else
            {
                Console.WriteLine("Не квадрат");
            }
        }

            int k = 0;
            for (int i = 0; i < n; i++) {

                if (dotX[i] >= dotX[0] && dotY[i] >= dotY[0] && dotX[i] <= dotX[2] && dotY[i] <= dotY[2])
                    k++;    
                }

            Console.WriteLine("Входит {0} точки",k);

            Console.ReadKey();

        }
    }
}

Kef1r вне форума   Ответить с цитированием
Старый 12.01.2017, 16:07   #8
ura_111
Профессионал
 
Регистрация: 14.05.2016
Сообщений: 1,495
Репутация: 263
По умолчанию

Вот набросал:

Код:

using System;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Количество точек: ");
            int n = Convert.ToInt32(Console.ReadLine());
            int[] X = new int[n];
            int[] Y = new int[n];
            Console.WriteLine("");
            Console.WriteLine("Введите координаты точек");
            for (int i = 0; i < n; i++)
            {
                Console.Write("X{0} = ", i + 1);
                X[i] = Convert.ToInt32(Console.ReadLine());
                Console.Write("Y{0} = ", i + 1);
                Y[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine("");
            
            int k_nov;  
            int k_st = -1;
            int i0, i1, i2, i3;
            int i0_st = -1, i1_st = -1, i2_st = -1, i3_st = -1;            
                    
            for (i0 = 0; i0 < n - 3; i0++)
            {
                for (i1 = i0 + 1; i1 < n - 2; i1++)
                {
                    for (i2 = i1 + 1; i2 < n - 1; i2++)
                    {
                        for (i3 = i2 + 1; i3 < n - 0; i3++)
                        {                          
                            if (proverka(X[i0], Y[i0], X[i1], Y[i1], X[i2], Y[i2], X[i3], Y[i3]) == 1)
                            {
                                k_nov = 0;
                                for (int i = 0; i < n; i++)
                                {
                                    if (X[i] >= X[i0] && Y[i] >= Y[i0] && X[i] <= X[i2] && Y[i] <= Y[i2])
                                        k_nov++;
                                }
                                if (k_nov > k_st)
                                {
                                    k_st = k_nov;
                                    i0_st = i0;
                                    i1_st = i1;
                                    i2_st = i2;
                                    i3_st = i3;
                                }
                            }
                        }                        
                    }                 
                }                
            }            

            if (k_st!=-1)
            {
                Console.WriteLine("Лучший квадрат: ({0},{1})-({2},{3})-({4},{5})-({6},{7})", X[i0_st], Y[i0_st], X[i1_st], Y[i1_st], X[i2_st], Y[i2_st], X[i3_st], Y[i3_st]);
                Console.WriteLine("к= {0}", k_st);
            }
            else { Console.WriteLine("Нет квадратов"); }
           
            Console.ReadKey();
        }

        public static int proverka(int X0, int Y0, int X1, int Y1, int X2, int Y2, int X3, int Y3)
        {
            double d1, d2, d3, di1, di2;

            d1 = Math.Sqrt(Math.Pow(X1 - X0, 2) + Math.Pow(Y1 - Y0, 2));
            d2 = Math.Sqrt(Math.Pow(X2 - X1, 2) + Math.Pow(Y2 - Y1, 2));
            d3 = Math.Sqrt(Math.Pow(X3 - X2, 2) + Math.Pow(Y3 - Y2, 2));

            di1 = Math.Sqrt(Math.Pow(X2 - X0, 2) + Math.Pow(Y2 - Y0, 2));
            di2 = Math.Sqrt(Math.Pow(X3 - X1, 2) + Math.Pow(Y3 - Y1, 2));
 
            if (Math.Abs(d1 - d2) < 0.0001 && Math.Abs(d2 - d3) < 0.0001 && Math.Abs(di1 - di2) < 0.0001)
            {
                return 1; // Квадрат
            }
            else
            {
                return 0; // Не квадрат
            }                      
        }     
    }
}

Протестируй (и не только на примере 11 узлов, а и на других количествах тоже). Прежде чем тестировать - нарисуй точки, чтобы представлять какие вошли, а какие нет в квадрат.
ura_111 вне форума   Ответить с цитированием
Старый 12.01.2017, 17:00   #9
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от ura_111 Посмотреть сообщение
Протестируй (и не только на примере 11 узлов, а и на других количествах тоже). Прежде чем тестировать - нарисуй точки, чтобы представлять какие вошли, а какие нет в квадрат.
Большое спасибо, все работает) Без вас бы не справился.
Kef1r вне форума   Ответить с цитированием
Ответ



Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Из заданного мн-ва точек на плоскости выбрать 3 разные точки A,B,C так,чтобы внутри треугольника ABC было максимальное число точек Ronin94 Общие вопросы C/C++ 4 02.02.2015 19:31
Среди N точек, заданных своими координатами на плоскости, определить самую дальнюю точку от начала координат. zaira001002 Общие вопросы C/C++ 10 30.09.2013 10:26
Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек) ExploiT243 Помощь студентам 1 27.05.2012 10:31
Задаnm n точек. Найти m=3,4... точек и построить на них m-угольник: количество точек , лежащих внутри и вне его мин. различается L.Rain Помощь студентам 0 11.12.2011 22:19
определить радиус и центр окружности, на кот. лежит наиб.число точек заданного на плоскости мн-ва точек) kcю Помощь студентам 0 17.11.2009 20:50




03:42.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.

купить трафик


как улучшить посещаемость, а также решения по монетизации сайтов, видео и приложений

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru