Геометрия Си/С++

[FleXt]

Из заданного множества точек на плоскости выбрать две различные точки так, чтобы количества точек, лежащих по разные стороны прямой, проходящей через эти точка, различались наименьшим образом.
Точки заданы координатами. Единственное что смог придумать это перебирать все пары точек, но это по времени получается достаточно долго.

[Abstraction]

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

Перебирать все пары и для каждой пары "в лоб" перебирать все остальные точки и определять, по какую сторону от прямой они легли - в худшем случае O(N^3). Многовато, но не так чтобы отвратительно. По идее, если только кто-то не выпрыгнул из своей шкуры, пытаясь расставить точки так, чтобы на всякой прямой было не меньше трёх, разность 0 или 1 мы получим достаточно рано.
Оптимизация: берём точку и все остальные точки загоняем в массив, дополняя каждую углом на неё из выбранной. Сортируем массив по углам. Теперь для каждой точки определение разности количества точек с одной и с другой стороны занимает логарифмическое время, всего в худшем случае O(N^2*lnN). Для чётного числа точек минимум 0 в среднем случае должен достигаться уже на первой-второй точке, что сокращает среднее время до O(N*lnN).
Для нечётного числа точек всё хуже: вполне может быть единственная тройка точек, лежащая на одной прямой, разделяющей все остальные точки на две равномощные группы. В этом случае ничего умнее полного перебора мне в голову не приходит.
А вот для чётного числа точек есть вторая оптимизация: взять произвольное направление прямой; найти, перебрав все точки, какая прямая с таким направлением делит множество точек пополам; если она неизбежно проводится по точкам и число этих точек нечётно - взять другое произвольное направление и повторить; если она может быть не проведена ни через одну точку - дальше попытаться чуть "подвинуть" или "довернуть" её. Если за несколько итераций этот алгоритм не срабатывает - значит, точки подобраны специально и очень аккуратно, рекомендуется возвращение к предыдущему алгоритму и полный перебор.

[FleXt]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 15


int main()
{   int i,j=0,k,n;
    int v, left, right, min;
    int x[N],y[N];
    int imn=0, jmn=0;
    scanf("%d", &n);
     for( i=0;i<n;i++)
        scanf("%d%d",&x[i],&y[i]);
     for(i=0;(i<n)&&(min!=0||min!=1);i++)
        {

         for(j=j+i;(j<n)&&(min!=0||min!=1);j++)
         {
             left=0;
             right=0;
            for(k=1;k<n;k++)
               {

                v=(x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]);
                if(v>0) left++;
                else if(v<0) right++;
               }
            min=abs(left-right);
         }
         imn=i;
         jmn=j;
        }
       printf("%d %d  %d %d",x[imn],y[imn],x[jmn],y[jmn]) ;
}

попытался написать, но не работает, где-то выхожу за размеры массива

[FleXt]

да и точка находится не правильная)

[FleXt]

     min=abs(left-right);
         }
         imn=i;
         jmn=j;
        }

вот тут ошибку нашел ,заменил на

 min=abs(left-right);
            imn=i;
           jmn=j;
         }

        }

но проблема осталась, ответ не правильный

[FleXt]

Сообщение от Abstraction

Перебирать все пары и для каждой пары "в лоб" перебирать все остальные точки и определять, по какую сторону от прямой они легли - в худшем случае O(N^3). Многовато, но не так чтобы отвратительно. По идее, если только кто-то не выпрыгнул из своей шкуры, пытаясь расставить точки так, чтобы на всякой прямой было не меньше трёх, разность 0 или 1 мы получим достаточно рано.
Оптимизация: берём точку и все остальные точки загоняем в массив, дополняя каждую углом на неё из выбранной. Сортируем массив по углам. Теперь для каждой точки определение разности количества точек с одной и с другой стороны занимает логарифмическое время, всего в худшем случае O(N^2*lnN). Для чётного числа точек минимум 0 в среднем случае должен достигаться уже на первой-второй точке, что сокращает среднее время до O(N*lnN).
Для нечётного числа точек всё хуже: вполне может быть единственная тройка точек, лежащая на одной прямой, разделяющей все остальные точки на две равномощные группы. В этом случае ничего умнее полного перебора мне в голову не приходит.
А вот для чётного числа точек есть вторая оптимизация: взять произвольное направление прямой; найти, перебрав все точки, какая прямая с таким направлением делит множество точек пополам; если она неизбежно проводится по точкам и число этих точек нечётно - взять другое произвольное направление и повторить; если она может быть не проведена ни через одну точку - дальше попытаться чуть "подвинуть" или "довернуть" её. Если за несколько итераций этот алгоритм не срабатывает - значит, точки подобраны специально и очень аккуратно, рекомендуется возвращение к предыдущему алгоритму и полный перебор.

Не могли бы Вы посмотреть мой код?

[Abstraction]

for(j=j+i

Это почему и зачем?
Почему переменные целочисленные и подумали ли Вы про округление?
Что за условие min!=1?
Почему K считается от 1?
И какие из этих проблем нельзя было обнаружить с помощью отладчика?..

[FleXt]

Сообщение от Abstraction

Это почему и зачем?
Почему переменные целочисленные и подумали ли Вы про округление?
Что за условие min!=1?
Почему K считается от 1?
И какие из этих проблем нельзя было обнаружить с помощью отладчика?..

for(j=j+i тк фиксирую первую точку, смотрю пары с остальными точками. Про целочисленные переменные не подумал. min!=1 а разве это не будет минимальной разностью? Четное количество точек можно разделить пополам, нечетное либо так же пополам, либо с одной стороны будет на 1 точку больше чем с другой, от сюда условие не равенства 1. К надо считать от нуля?

[Abstraction]

for(j=j+i тк фиксирую первую точку, смотрю пары с остальными точками.

К середине времени работы программы, j=5, i=12. Счёт j в цикле начнётся со значения 17. Я не в силах понять стоящей за этим логики.

min!=1 а разве это не будет минимальной разностью? Четное количество точек можно разделить пополам, нечетное либо так же пополам, либо с одной стороны будет на 1 точку больше чем с другой, от сюда условие не равенства 1.

*вырезано цензурой*

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

К надо считать от нуля?

Отвечаем вопросом на вопрос? Не знаю... может надо, может не надо. Но Вы организовали цикл так, что k пробегает значения от 1 до n-1. Я интересуюсь: почему Вы приняли такое решение.

[FleXt]

for(i=0;(i<n)&&(min!=0||min!=1);i++ )
{

for(j=i+1;(j<n)&&(min!=0||min!=1);j ++)
{
left=0;
right=0;
for(k=j+1;k<n;k++)
{

v=(x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]);
if(v>0) left++;
else if(v<0) right++;
}
min=abs(left-right);
imn=i;
jmn=j;
}

}

сделал вот так