Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

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

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

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

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

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

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

У меня есть код на паскале, но программа не верно считает количество точек.
Мне бы сначала разобраться почему, а потом переделать на 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 Кб, 164 просмотров)
Kef1r вне форума Ответить с цитированием
Старый 09.01.2017, 13:03   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

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

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

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

Сделал для 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, 15:07   #8
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

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

Код:
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, 16:00   #9
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Из заданного мн-ва точек на плоскости выбрать 3 разные точки A,B,C так,чтобы внутри треугольника ABC было максимальное число точек Ronin94 Общие вопросы C/C++ 4 02.02.2015 18: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 19:50