Общая длина точек

[dimon_snake]

Здравствуйте, нужна помощь.
Дано n точек, и их координаты.
Нужно узнать общую длину между точками, учитывая, что некоторые точки
могут лежать на одной прямой. То есть, если точки 2, 3, 4 лежат на одной прямой, то не нужно узнавать и добавлять расстояние между 2 и 3, 2 и 4, 3 и 4.
Так то понятно, находит, подходит ли уравнение прямой, лежат ли точки на одной прямой, считаем и отнимаем. А вот что сделать, если на одной прямой более трех точек, ведь точек на одной прямой может быть хоть n.
Помогите, пожалуйста, подскажите, может какой алгоритм не знаю.
Вот код:

type
gorod = record
k1,k2:integer;\\для координат
end;
pryam = record
g1,g2,g3:integer;\\для уравнений прямой
end;
var
cit:array[1..100] of gorod;\\n максимум 100
pryama:array[1..100] of pryam;
mat:array[1..100,1..100] of integer;\матрица смежности
fi,fo:text;
i,z,j,y,k:integer;
sum:longint;
begin
Assign(fi,'roads.in');
Assign(fo,'roads.out');
REset(fi);
REwrite(fo);
REad(fi,z);\\читаем n
for i:=1 to z do
for j:=1 to z do
mat[i,j]:=0;\\заполняем матрицу нулями
for i:=1 to z do
begin
  Readln(fi);
  Read(fi,cit[i].k1,cit[i].k2);\\читаем координаты
end;
y:=1;\\счетчик количества уравнений прямых
for i:=1 to z do \\цикл на поиск уравнений прямых
begin
  for j:=i+1 to z do
  begin
    for k:=j+1 to z do
    begin
      if ((cit[k].k1-cit[i].k1)*(cit[j].k2-cit[i].k2)=(cit[k].k2-cit[i].k2)*(cit[j].k1-cit[i].k1))\\если таковое есть
      then
      begin
        pryama[y].g1:=i;\\кидаем номера городов в массив
        pryama[y].g2:=j;
        pryama[y].g3:=k;
        Inc(y);
      end;
    end;
  end;
end;
for i:=1 to z do
  for j:=1 to z do
    mat[i,j]:=Round(sqrt(sqr(cit[i].k1-cit[j].k1)+sqr(cit[i].k2-cit[j].k2)));\\заполняем матрицу смежности расстояниями между городами
sum:=0;
for i:=1 to y-1 do\\считаем длину с уравнением прямой
begin
  sum:=sum-mat[pryama[i].g1,pryama[i].g2];
  sum:=sum-mat[pryama[i].g1,pryama[i].g3];
  sum:=sum-mat[pryama[i].g2,pryama[i].g3];\\то есть отнимаем то, что в следующем цикле будем добавлять
  sum:=sum+mat[pryama[i].g1,pryama[i].g2];\\добавляем расстояние отрезка, которые соединяет три города
end;
for i:=1 to z do
  for j:=1 to z do
  begin
    sum:=sum+mat[i,j];\\считаем расстояния между остальными городами
    mat[j,i]:=0;
  end;
Write(fo,sum);
close(fo);
end.

[Poma][a]

И снова ссылку

[dimon_snake]

и снова тот же, пятая.
http://olimpmoippo.pp.ua/

[Poma][a]

#include <fstream>
#include <set>
#include <vector>
#include <algorithm>

#define eps 1e-3

using namespace std;

ifstream cin("roads.in");
ofstream cout("roads.out");

struct point
{
	double x, y;
};

struct line
{
	double a, b, c;
	line(point p1, point p2)
	{
		// (x-x1)/(x2-x1)=(y-y1)/(y2-1)
		// (x-x1)*(y2-y1)=(y-y1)*(x2-x1)
		// x*(y2-y1)-(y-y1)*(x2-x1)=x1*(y2-y1)-y1*(x2-x1)

		//ax+by=c
		a = p2.y - p1.y;
		b = -(p2.x - p1.x);
		c = p1.x*(p2.y - p1.y) - p1.y*(p2.x - p1.x);
	}
	bool in(point p)
	{
		return fabs(p.x*a + p.y*b - c) < eps;
	}
};

bool operator < (const point& p1, const point& p2)
{
	return p1.x < p2.x || fabs(p1.x - p2.x) < eps  && p1.y < p2.y;
}

double dist(const point& p1, const point& p2)
{
	return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

bool operator > (const point& p1, const point& p2)
{
	return !(p1 < p2);
}

int main()
{
	int n;
	cin >> n;
	vector<point> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].x >> v[i].y;

	double ans = 0;
	set<pair<point, point> > s;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			line l = line(v[i], v[j]);
			point mi = min(v[i], v[j]);
			point ma = max(v[i], v[j]);
			for (int k = 0; k < n; k++)
				if (l.in(v[k]))
				{
					mi = min(mi, v[k]);
					ma = max(ma, v[k]);
				}
			if (s.find(make_pair(mi, ma)) == s.end())
			{
				ans += dist(mi, ma);
				s.insert(make_pair(mi, ma));
			}
		}			
	}

	cout << (int)(ans+0.50);
	return 0;
}

На 90.
Ошибку пока не вижу

[Poma][a]

Можно, кстати, сделать что-то похожее на квадрат. Но это улучшит лишь время. А писанины больше. Да и лень мне..

[dimon_snake]

Спасибо. А можно подробнее о коде? Не особо знаю с++, переведу.

[dimon_snake]

Вот что хотелось бы узнать:
vector<point> v(n); - это создание массива v с элементами point, при это n элементов
set<pair<point, point> > s; - это строку в паскале как можно представить, не пойму
line l = line(v[i], v[j]); - вот эта не понятна, что за тип line
if (s.find(make_pair(mi, ma)) == s.end()) - вот эта неясная
s.insert(make_pair(mi, ma)); - и вот эта
Все остальное вроде ясно

[Poma][a]

Пойми алгоритм и перепиши его как тебе захочется.

Set позволяет за логарифм вставлять и искать элемент
Пара поинтов это все равно что структура с двумя полями first и second типа point

[dimon_snake]

Можете тогда просто объяснить алгоритм?

[Poma][a]

Через каждые две точки проводишь прямую. Запоминаешь её. Ищешь на две самые удаленные точки - а затем плюсуешь расстояние между ними
И так делаешь для всех точек но важно проверить что прымую которую ты нашёл ты раньше не использовал
Я делал это запоминая две точки. Можно это провернуть через общее уравнение прямой.