есть массив целочисленных пар (x,y) - точки на плоскости. Определить обладает ли множество точек массива осевой симметрией

(0) Идея такая:

Легко проверить, что множество точек осесимметрично относительно оси X (или Y - тогда рассуждения те же, но относительно другой оси).
Предположим, что ось симметрии существует. Тогда её можно поворотом на угол phi перевести в ось X.
При этом координаты точек преобразуются так:
x' = x cos phi + y sin phi
y' = -x sin phi + y cos phi
Если множество осесимметрично относительно оси X, то сумма y-координат будет равна 0. Отсюда
tg phi = X/Y,
где X - сумма x-координат исходных точек, а Y - сумма y-координат исходных точек.
Поворачиваем множество исходных точек на этот угол - и проверяем, симметрично ли оно относительно оси X.

>>Если множество осесимметрично относительно оси X, то сумма y-координат будет равна 0.
Обратное не верно, да и выбор угла сомнения вызывает

(1) А обратное и не нужно. Это необходимое условия. _После_ преобразования - проверка.

Насчёт выбора угла - просто подставь, затем вынеси sin и cos за скобки.

(1) А про параллельный перенос не забыли? Вдруг ось симметрии не совмещается с осью координат одним только поворотом (Пример: искомая ось симметрии Y=7)?

а мне кажется, что ось может быть из точек массива

имхо тока имперически:
либо дробим всю область сеткой и проверяем в каждом узле все 360 градусов
либо по окружности вокруг каждой точки проверяем все возможные точки на окружности + все 360 градусов

(7) Забыл.
Но можно предварительно "отцентровать" множество.

(6) Зачем же так жестоко?
Даже если перебором - то зачем всю плоскость-то перебирать? Ось симметрии заведомо будет серединным перпендикуляром к какому-нибудь из отрезков (кроме вырожденного случая, когда все точки лежат на одной прямой).

(1) если суммы координат по X и по Y дают нули?

(0) чую какойто задачник олимпиадный покоя не дает)))

(9) Дают. И даже очень часто :-(

Тогда есть такой вариант: "центрируем" множество точек, вычитая из каждого радиус-вектора 1/n \Sigms r_k, где r_k - радиус-векторы точек.

Находим точки с максимальным расстоянием до центра.

(Возможная) ось симметрии будет проходить либо через центр и одну из "максимальных" точек, либо через центр и середину отрезка между двумя "максимальными" точками.

Проверяем все возможные оси.

Перебором, конечно, неприятно - но хоть какой-то вариант.

+(11) Нет, вредно заниматься 1С :-(
В (11) - тоже бред написан.

(12) почему бред?

(13) Не совсем бред.
Можно сложить координаты "отцентрованного" множества. Если не 0 - то это единственная возможная ось симметрии.
Если же 0 - то не пойму, можно ли взять любую пару точек и соединить центр с серединой отрезка, или же всё равно нужно все проверять.

+(14) Имеется в виду, просуимировать "максимальные" точки.

+(14) Разумеется, все отрезки проверять. Поскольку есть и "внутренние" точки.
Разве что число вариантов сократить, отсортировав точки по углу и проверяя лишь соседние.

Частный вариант если точки не лежат на оси симметрии:

Допустим точек всего N. Тогда условие симметрии соблюдается тогда, если можно разбить N на такие пары, что мат среднее координат каждой пары Xср = (X1 + X2)/2, Yср = (Y1+Y2)/2 (короче говоря точка посередине) удовлетворяет уравнению У
= KX + H; K и H находятся для первых двух пар.

Количество проверок равно кол-во сочетаний из N по 2 (т.е каждую точку с каждой другой). Таких будет N!/2!(N-2)! = N(N-1)/2

Для случаев когда есть точки на оси просто дубируем в массив каждую точку и проверяем, всего проверок тогда будет N(2N-1)

*Дублируем

(17) С подсчетом проверок я ошибся, но принцип такой же.

(0) найти четыре точки:
(max x; max y)
(max x; min y)
(min x; max y)
(min x; min y)
ну и проверить на симметрию

(20) Например, точки
(0,),(0,10),(5,6),(7,8),(10,0),(10,10).

Что имеется в виду под проверкой на симметрию в этом случае?

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

1 (10,10)
2 (10,0)
3 (0,10)
4 (0,0)

(22)+ еще надо учитывать оси (линии) симметрии у проверенных точек

struct Point
   {
       public double X { get; set; }
       public double Y { get; set; }
       public static Point operator -(Point a, Point b)
       {
           return new Point() { X = a.X - b.X, Y = a.Y - b.Y };
       }
       public bool IzZero()
       {
           return (X == 0) && (Y == 0);
       }
       public Line Line(Point b)
       {
           if (this.X == b.X)
           {
               return new Line() { A = 1, B = 0, C = -this.X };
           }
           if (this.Y == b.Y)
           {
               return new Line() { A = 0, B = 1, C = -this.Y };
           }
           Point r = this-b;
           return new Line() {A=1/r.X, B=-1/r.Y, C=b.Y/r.Y-this.X/r.X};
       }
       public Point SegmentCenter(Point b)
       {
           return new Point() { X = (this.X + b.X) / 2, Y = (this.Y + b.Y) / 2 };
       }
   }
   struct Line
   {
       public double A { get; set; }
       public double B { get; set; }
       public double C { get; set; }
       public Line Orthogonal(Point p)
       {
           Line Result = new Line();
           if (this.A == 0)
           {
               Result.B = 0;
               Result.A = 1;
           }
           else
           {
               Result.B = 1;
               Result.A = -this.B / this.A;
           }
           Result.C = -Result.Value(p);
           return Result;
       }
       public bool InLine(Point p)
       {
           return (Value(p)+C == 0);
       }
       private double Value(Point p)
       {
           return (A * p.X + B * p.Y);
       }
       public bool Equal(Line s)
       {
           double k;
           if (this.A == 0)
           {
               if (s.A != 0)
                   return false;
               k = s.B / this.B;
           }
           else
               k = s.A / this.A;
           return (this.B * k == s.B) && (this.C * k == s.C);
       }
   }

class Program
   {
       static void Main(string[] args)
       {
           const int n = 4;
           Point[] a = new Point[n]
               {
                   new Point() {X=0, Y=0},
                   new Point() {X=0, Y=1},
                   new Point() {X=1, Y=0},
                   new Point() {X=1, Y=1}
               };
           Point c = new Point() { X = a.Average(p => p.X), Y = a.Average(p => p.Y) };
           Point[] b = a.Select(p => p - c).ToArray();
           bool Simmetric = true;
           Point Zero = new Point();
           foreach (Point p in b)
           {
               if (p.IzZero())
                   continue;
               if (Test(p.Line(Zero), b))
                   break;
               bool IsSimmetric=false;
               foreach (Point q in b)
               {
                   Line s;
                   if ((p - q).IzZero())
                       continue;
                   else
                       s = p.Line(q).Orthogonal(p.SegmentCenter(q));
                   if (!s.InLine(Zero))
                       continue;
                   IsSimmetric = Test(s, b);
                   if (IsSimmetric)
                       break;
               }
               Simmetric = IsSimmetric;
               break;
           }
           Console.WriteLine("{0}", Simmetric);
           Console.ReadKey();
       }
       private static bool Test(Line s, Point[] a)
       {
           List<int> index = new List<int>();
           bool Result = true;
           for (int i = 0; i < a.Length; i++)
           {
               if ((index.Contains(i)) || (s.InLine(a[i])))
                   continue;
               bool FoundSimmetric = false;
               for (int j = i + 1; j < a.Length; j++)
               {
                   if ((index.Contains(i)) || ((a[i] - a[j]).IzZero()))
                       continue;
                   FoundSimmetric = a[i].Line(a[j]).Orthogonal(a[i].SegmentCenter(a[j])).Equal(s);
                   if (FoundSimmetric)
                   {
                       index.Add(j);
                       break;
                   }
               }
               if (!FoundSimmetric)
               {
                   Result = false;
                   break;
               }
           }
           return Result;
       }
   }

(0) Подойдем физически. Если ось симметрии существует, она проходит через центр тяжести с координатами: Х=сумма(х)/N; Y=сумма(y)/N.
Сместим туда центр координат: x'=x-X; y'=y-Y.
В новых координатах сумма(x)=0 и  сумма(y)=0.
Заметим, опять-таки, что если ось симметрии существует, то она проходит через точку с координатами: XХ=сумма(w*х')/N; YY=сумма(w*y')/N, где w - весовая функция, имеющая одинаковое значение для симметричных пар. Например, w = x'^2 + y'^2 (расстояние до ц.т.).
Если точки (X,Y) и (XX,YY) не совпадают, то мы имеем прямую, проходящую через них, которая могла бы претендовать на роль оси симметрии. Осталось это проверить. Если точки совпали, то из соображений симметрии мы имеем либо несколько осей симметрии, либо центр симметрии. По-любому, ответ на вопрос задачи в этом случае - да.

(25) мне понравилось
но насчет центра симметрии? в задаче просят проверить на осевую симметрию

(25) "Если точки совпали, то из соображений симметрии" тоже довольно туманно
Может подобрать тогда другую функцию веса?

(26) При дискретном наборе точек центральная симметрия вырождается в несколько осей симметрии. Та что ответ однозначный. Вот если было тело произвольной формы с распределением плотности, тогда...  :0) Попробуйте привести центрально симметричное расположение точек, при котором нет хотя бы одной оси симметрии. :0)
(27) Чтобы точки не совпали при центрально-симметричном расположении, нужна весовая функция, нарушающая эту симметрию, но при этом одинаковая для симметричных пар. Любая w(R), где R - расстояние до ц.т., такой симметрии не нарушает. А поскольку мы не знаем, какие точки собраны в пары, то я плохо представляю, как можно подобрать функцию с одинаковым для них значением. Хотя, может надо просто еще хорошенько подумать...  :0)

(28) звездочки точки, подчеркивания пустые места
_**
_*_
**_
если функция w2(x,y)=x^2+y^2 не подходит, то возможно подойдет w3(x,y)=x^3+y^3
в общем скорее всего для некоторого n: wn(x,y)=x^n+y^n

Находим центр тяжести, затем проводим луч через центр тяжести и каждую точку.
Сортируем по углу. По каждуму полученной прямой проверяем на симметрию, и для каждой пары "соседних" лучей проведя биссектриссу проверяем на симметрию.
Сложность получается макс(N*сложность_проверки_на_осевую_симетрию_при_Заданной_оси,N*Ln N) - второе - это сортировка лучей по углу.

Есно перед проверкой на симметрию за сложность N можно сравнить число точек "справа" и "слева" от луча.

(30) для каждой пары не надо, достаточно для точки отличной от центра и каждой другой.
Проверка прямой на ось это N*N
Не понял, что дает сортировка по углу?
У меня получается N*N*N

(29) Пардон, отвлекли.
Насчет центрально-симметричных звездочек - ваша правда...  :0)
А вот w3 не подойдет. При произвольном положении осей (не совпадающими с осью симметрии) весовая функция будет разной для пары симметричных точек.
И даже если оси совпадают: берем 4 точки (2,1), (2,-1), (-2,1) и (-2,-1).
Имеем (XX,YY)=(64/4, 4/4)=(8,1) - не лежит на оси симметрии.

(33) нужно брать |x-x0|^n+|y-y0|^n , где x0,y0 - центр масс

Основная идея введения весовой функции заключается в том, чтобы сместить центр масс "взвешенной" системы. Если при этом назначении весов не нарушать осевой симметрии, то новый ц.м. тоже будет лежать на оси симметрии. Без нарушения общности будем считать, что точка отсчета совпадает с ц.м. при w=1. Тогда весовая фунция w должна быть инвариантна относительно поворота осей (иными словами, не зависеть от того, как мы кинем свою систему координат относительно оси симметрии). Иначе во "взвешенной" системе нарушится осевая симметрия. Поскольку R (расстояние до ц.м.) обладает такой инвариантностью, то ее будет обладать и любая функция w(R). Но при этом у w нет градиента вдоль оси симметрии и ожидать, что новый ц.м. сместится довольно сложно. Предложенный вами вариант инвариантностью относительно поворота не обладает.

(35) с чего бы?

(24) круто. сам задаешь задачу, сам ее решаешь...а слабо решить чужую?

(37) я эту задачу взял с другого форума, мне стало интересно
давай задачу

(37) если интересная, займусь

(39)Есть куча "золотого песка"  и N человек. (больше нет ничего). как разделить эту кучу между ними что бы не было претензий после дележки ?

(40) эта задача о бандитам из книги Гарднера. По-моему, здесь она тоже была. Потому неинтересная.

(41)ну я вижу ты в "теме". тогда предлогаю не мерятся пиписками)) Серьезную и интересную задачу искать надо, это не быстро

(42) согласен

(43) студенческие олимпиады интересны? или только школьные?

(44) всякие: математика и программирование

(36) Потому что при повороте осей координат у вас будет меняться |x-x0| и |y-y0|. Подставьте замену координат при повороте осей и увидите зависимость от угла. Если x0=0 и y0=0, то выражение примет вид |x|^n+|y|^n и будет инвариантно только при n=2 ( ибо sin^2 + cos^2 = 1 ).

Вот накатал:

http://ifolder.ru/13814387

Обработка 1С8.1  Пока косяков не нашел, все определяет. В ТЧ вводятся точки, (колонки X Y ) по кнопке Выполнить сообщает Истина - есть симметрия, Ложь - нету.

(47) Для набора
1,1
0,1
-1,1
1,-1
0,-1
-1,-1
говорит ложь...
:0)

(48) Нашел косяк. Выполнялось только если первые две точки находятся в симметрии относительно общей оси. Вот код должен работать:


Процедура КнопкаВыполнитьНажатие(Кнопка)
   K = Неопределено;
   H = Неопределено;
   ТЗ = Точки.Выгрузить();
   Рез = ПроверитьТочки(ТЗ, K, H);
   Сообщить(Рез);
КонецПроцедуры


Функция ПроверитьТочки(ТЗ, K = Неопределено, H = Неопределено)
   
   N = ТЗ.Количество();
   Если N = 1  Тогда
       Возврат Ложь;
   КонецЕсли;    
   
   Если N = 0  Тогда
       Возврат Истина;
   КонецЕсли;    
   
   Для i = 0 По N-2 Цикл
       
       Для j = i+1 По N-1 Цикл
           
           
           ТЗ1 = ТЗ.Скопировать();
           
           Pi = ТЗ1[i];
           Pj = ТЗ1[j];
           
           Xf = (Pi.x + Pj.x)/2;
           Yf = (Pi.y + Pj.y)/2;
           
           Kij = ?(Pi.y - Pj.y = 0, NULL, (Pi.x - Pj.x)/(Pj.y - Pi.y));
           Hij = ?(Pi.y - Pj.y = 0, Xf , Окр(Yf - Xf * Kij,  5));
       
           
           Если K = Неопределено Тогда
               //K = Kij;
               //H = Hij;
           Иначе
               Если K <> Kij ИЛИ H <> Hij Тогда
                   Продолжить;
               КонецЕсли;
           КонецЕсли;
           ТЗ1.Удалить(Pi);
           ТЗ1.Удалить(Pj);
           //Также удалить все точки лежащие на этой прямой
           
           Кол = ТЗ1.Количество();
           Для Итер = 0 по Кол -1 Цикл
               СтрокаПроверки = ТЗ1[Кол - Итер - 1];
               Если Kij = NULL Тогда
                   Удалить = (СтрокаПроверки.x = Hij);
               Иначе
                   Удалить = (СтрокаПроверки.y =   Окр(СтрокаПроверки.x * Kij,  5) + Hij);
               КонецЕсли;
               Если Удалить Тогда
                   ТЗ1.Удалить(СтрокаПроверки);
               КонецЕсли;
            КонецЦикла;
           
           
           Рез = ПроверитьТочки(ТЗ1, Kij, Hij );
           Если Рез = Истина Тогда
               Возврат Истина;    
           КонецЕсли;
       КонецЦикла;
   КонецЦикла;
   Возврат Ложь;    
   
КонецФункции

Процедура ПриЗакрытии()
   СохранитьЗначение(Точки.Выгрузить(), "ТЗ_11111111");
   
КонецПроцедуры

Процедура ПриОткрытии()
   Т = Точки.Добавить();
   Т.X = -1;
   Т.Y = 1;
   
   Т = Точки.Добавить();
   Т.X = 0;
   Т.Y = 1;
   
   Т = Точки.Добавить();
   Т.X = 1;
   Т.Y = 1;
   
     Т = Точки.Добавить();
   Т.X = -1;
   Т.Y = -1;
   
   Т = Точки.Добавить();
   Т.X = 0;
   Т.Y = -1;
   
   Т = Точки.Добавить();
   Т.X = 1;
   Т.Y = -1;

   
КонецПроцедуры

(49) Берем точки (-2,0), (1,1) и (1,-1). Ц.М в точке (0,0). Ось симметрии совпадает с осью X.
Теперь повернем систему из трех точек на 30 градусов по часовой стрелке и сожмем в sqrt(2) раз.
Получится три точки с координатами:


Процедура ПриОткрытии()
   
   Pi=3.1415926535897932;
   Угол = Pi / 12;      //15 градусов
   Кос15 = Cos(Угол);
   Син15 = Sin(Угол);
   
  Т = Точки.Добавить();
  Т.X = -SQRT(3/2);
  Т.Y = SQRT(1/2);
   
  Т = Точки.Добавить();
  Т.X = Кос15;
  Т.Y = Син15;
   
  Т = Точки.Добавить();
  Т.X = Син15;
  Т.Y = -Кос15;
   
КонецПроцедуры


Обработка обманывает, говорит ЛОЖЬ...  :0)
Только точность у Точки.X и Точки.Y поменяйте...  :0)