VPF::задачка - Форум программистов

f999t1

Дата 19.10.2008, 21:06 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 11.4.2006

Репутация: нет
Всего: нет

даны точки на плоскости(в txt файле заданы координаты).
Надо найти положение на плоскости треугольника с целочисленными координатами вершин,внутри которого находится максимальное число точек.

Подскажите идею в поиске такого треугольника

eyeofhell

Дата 19.10.2008, 21:46 (ссылка)

(нет голосов)

Загрузка ...

Адепт

Профиль
Группа: Участник
Сообщений: 87
Регистрация: 16.10.2008
Где: Россия, Москва

Репутация: 1
Всего: 1

Пропущено какое-то условие. Берешь любой треугольник с координатами в миллион раз больше самых больших/маленьких координат точек - все точки гарантировано будут там.

Наверное есть ограничение на площадь треугольника, его координаты?

Dmi3ev

Дата 19.10.2008, 23:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

вот функция, которая проверяет, находится ли точка внутри треугольника:

Код


//---------------------------------------------------------------------------

#include <vcl.h>
#include <mypoint.h>
#include <mysegment.h>
#pragma hdrstop

#include "tr_U.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
long double SGeron (MySeg a, MySeg b, MySeg c)
{
 long double p=(a.Length()+b.Length()+c.Length())/2;
 return sqrt(p*(p-a.Length())*(p-b.Length())*(p-c.Length()));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
MyPoint A(1,2), B(2,8), C(1,6);
MyPoint P(1,1);
MySeg AB(A,B), BC(B,C), AC(A,C);
MySeg AP(A,P), BP(B,P), CP(C,P);
long double s, s1, s2, s3;
s=SGeron(AB, BC, AC);
s1=SGeron (AB, AP, BP);
s2=SGeron (BC, BP, CP);
s3=SGeron (AC, AP, CP);
if ((s1+s2+s3)>s)
 MessageBox(NULL, "Точка вне треугольника!", "Сообщение", MB_OK);
else
 MessageBox(NULL, "Точка внутри треугольника!", "Сообщение", MB_OK);
Edit1->Text=FloatToStr(s);
Edit2->Text=FloatToStr(s1);
Edit3->Text=FloatToStr(s2);
Edit4->Text=FloatToStr(s3);
}
//---------------------------------------------------------------------------

правда в билдере сделано, но это не суть важно, по-моему.
а вот подключаемые файлы:

Код


#include <mypoint.h>
#include <math.h>
#define XX(x) ((x)*(x))
class MySeg
{
public:
 MySeg (MyPoint A, MyPoint B)
  {
   p1=A; p2=B;
  };
 void Set (MyPoint A, MyPoint B)
  {
   p1=A; p2=B;
  };
 long double Length ()
  {
   return sqrt(XX(p1.Gety()-p2.Gety())+XX(p1.Getx()-p2.Getx()));
  };
 ~MySeg (){};
private:
 MyPoint p1, p2;
};

и второй:

Код


#ifndef MYPOINT_H
#define MYPOINT_H
class MyPoint
{
public:
MyPoint(double a=0.0, double b=0.0){x=a; y=b;};
void Set(double a, double b){x=a; y=b;};
double Getx(){return x;};
double Gety(){return y;};
~MyPoint(){};
private:
double x, y;
};
#endif

это является ключом к решению задачи, проверять, лежит ли точка внутри или нет. возможно у кого-то есть другие идеи, но я бы так делал.

--------------------

f999t1

Дата 19.10.2008, 23:52 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 11.4.2006

Репутация: нет
Всего: нет

да, насчет условия , треугольник составляется из точек в файле.

to Dmi3ev: можно поподробнее в словах про алгоритм определения
принадлежности точек
триугольнику (код не надо).

Это сообщение отредактировал(а) f999t1 - 19.10.2008, 23:53

Dmi3ev

Дата 19.10.2008, 23:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

ну смотри, если точка в треугольники, то площадь треугольника равна сумме площадей треугольников, образованных этой точкой и сторонами треугольника (их будет три). площади определяешь по формуле Геррона.

--------------------

f999t1

Дата 20.10.2008, 00:12 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 11.4.2006

Репутация: нет
Всего: нет

понятно

ну а возвращяясь к первоначальной задаче,
получается надо перебрать n*(n-1)*(n-2) треугольников для каждого из которых
надо тоже перебором оставшихся точек определить их принадлежность ему,
а потом из всех треугольников определить тот который удовлетворяет условию.

Может есть алгоритм который решает эту задачу побыстрее?

Dmi3ev

Дата 20.10.2008, 00:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

Цитата

ну, надо же не все точки тупо пробовать, некоторые можно исключать заранее, а дальше можно еще что-то придумать smile

начни, там видно будет smile

по-любому эта проверка пригодится, пока реализуй функцию проверки, лежит ли точка в треугольнике, а потом уже видно станет, как и чего

--------------------

f999t1

Дата 20.10.2008, 00:21 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 65
Регистрация: 11.4.2006

Репутация: нет
Всего: нет

ОК! Спасибо
Буду считать вопрос закрытым.

bsa

Дата 20.10.2008, 11:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

f999t1, для начала можно попробовать просто найти три точки, расстояние между любыми парами которых максимальное (D = sqrt((x1-x2)^2 + (y1-y2)^2). Из них составить треугольник... Но это очень приблизительный метод, который еще нужно проверить.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »