#include <stdlib.h>
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
int points[][2] = {
128, 24, 15, 20, 66, 26, 69, 81, 22, 73, 191, 180, 134, 72, 145, 127,
182, 90, 18, 127, 81, 128, 150, 168, 185, 129, 22, 173, 182, 15, 83, 177};
int compare( const void *arg1, const void *arg2 )
{
if(*(int *)arg1==*(int *)arg2)
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
else
return *(int *)arg1 - *(int *)arg2;
}
int main()
{
qsort(points, sizeof(points)/8, 8, compare);
for(int i = 0; i<sizeof(points)/8; i++)
cout << setw(4) << points[0] <<" "<< setw(4) << points[1] << endl;
cout << endl << "Press any key..." << endl;
getch();
return 0;
}
Сортировка двумерного массива. Хитрая...
Задача. Есть массив координат точек (X, Y) который не упорядочен. Нужно пересортировать массив так, чтобы координаты стояли в таком порядке, что соответствующие им точки располагались бы на картинке последовательно, например, первый элемент массива - это верхняя левая точка, второй элемент - вторая сверху точка в первом столбце. и так далее.
Сложность в том что точки располагаются на картинке не "квадратно-гнездовым" способом, а с небольшими отклонениями (как показано на прикрепленной картинке). Идеи по реализации алгоритма?
Вот пример неупорядоченного массива координат точек (примерно соответствует тому что на изображении):
128 24
15 20
66 26
69 81
22 73
191 180
134 72
145 127
182 90
18 127
81 128
150 168
185 129
22 173
182 15
83 177
Сложность в том что точки располагаются на картинке не "квадратно-гнездовым" способом, а с небольшими отклонениями (как показано на прикрепленной картинке). Идеи по реализации алгоритма?
Вот пример неупорядоченного массива координат точек (примерно соответствует тому что на изображении):
128 24
15 20
66 26
69 81
22 73
191 180
134 72
145 127
182 90
18 127
81 128
150 168
185 129
22 173
182 15
83 177
Так уточни же условие. У тебя нарисованы точки, которые всё равно создают квадратную сетку, пусть и немного кривую. То есть в каждом столбце и в каждой строке одинаковое количество точек. А по условию задачи всегда так будет? А если в первой строке будет больше строк, чем во второй? Тогда вообще некорректно говорить о столбцах и строках.
Проще всего использовать ф-ю qsort:
и можно еще данные загнать в set(или multiset если точки не уникальны)
Код:
Код:
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
#include <set>
int points[][2] = {
128, 24, 15, 20, 66, 26, 69, 81, 22, 73, 191, 180, 134, 72, 145, 127,
182, 90, 18, 127, 81, 128, 150, 168, 185, 129, 22, 173, 182, 15, 83, 177};
using namespace std;
struct TPointRec
{
int x;
int y;
TPointRec(const int in_x, const int in_y)
{
x = in_x;
y = in_y;
}
bool operator<(const TPointRec& O) const
{
if(x==O.x)
return y > O.y;
else
return x < O.x;
}
};
typedef set<TPointRec>TPoints;
int main()
{
TPoints pts;
for(int i = 0; i<sizeof(points)/8; i++)
pts.insert(TPointRec(points[0], points[1]));
for(TPoints::iterator it = pts.begin(); it!=pts.end(); it++)
cout << setw(4) << (*it).x <<" "<< setw(4) << (*it).y << endl;
cout << endl << "Press any key..." << endl;
getch();
return 0;
}
#include <iomanip.h>
#include <iostream.h>
#include <set>
int points[][2] = {
128, 24, 15, 20, 66, 26, 69, 81, 22, 73, 191, 180, 134, 72, 145, 127,
182, 90, 18, 127, 81, 128, 150, 168, 185, 129, 22, 173, 182, 15, 83, 177};
using namespace std;
struct TPointRec
{
int x;
int y;
TPointRec(const int in_x, const int in_y)
{
x = in_x;
y = in_y;
}
bool operator<(const TPointRec& O) const
{
if(x==O.x)
return y > O.y;
else
return x < O.x;
}
};
typedef set<TPointRec>TPoints;
int main()
{
TPoints pts;
for(int i = 0; i<sizeof(points)/8; i++)
pts.insert(TPointRec(points[0], points[1]));
for(TPoints::iterator it = pts.begin(); it!=pts.end(); it++)
cout << setw(4) << (*it).x <<" "<< setw(4) << (*it).y << endl;
cout << endl << "Press any key..." << endl;
getch();
return 0;
}
[QUOTE=Мerlin]Проще всего использовать ф-ю qsort:
[/QUOTE]
Умопомрочительная смесь из С и С++, использование void* и пр. приемов запутывания противника и привлечения багов.
Потрясающе:
А вот это вообще перл:
кто бы мог подумать, что это приращение указателя путем привода его к числовому типу увеличению на размер указателя, обратному приведению к типу указателя и разыменованию!
Если это "проще всего", то я даже боюсь за сложные решения. :D
Код:
#include <stdlib.h>
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
int points[][2] = {
128, 24, 15, 20, 66, 26, 69, 81,
22, 73, 191, 180, 134, 72, 145, 127,
182, 90, 18, 127, 81, 128, 150, 168,
185, 129, 22, 173, 182, 15, 83, 177};
int compare( const void *arg1, const void *arg2 )
{
if(*(int *)arg1==*(int *)arg2)
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
else
return *(int *)arg1 - *(int *)arg2;
}
int main()
{
qsort(points, sizeof(points)/8, 8, compare);
for(int i = 0; i<sizeof(points)/8; i++)
cout << setw(4) << points[0] <<" "<< setw(4) << points[1] << endl;
cout << endl << "Press any key..." << endl;
getch();
return 0;
}
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
int points[][2] = {
128, 24, 15, 20, 66, 26, 69, 81,
22, 73, 191, 180, 134, 72, 145, 127,
182, 90, 18, 127, 81, 128, 150, 168,
185, 129, 22, 173, 182, 15, 83, 177};
int compare( const void *arg1, const void *arg2 )
{
if(*(int *)arg1==*(int *)arg2)
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
else
return *(int *)arg1 - *(int *)arg2;
}
int main()
{
qsort(points, sizeof(points)/8, 8, compare);
for(int i = 0; i<sizeof(points)/8; i++)
cout << setw(4) << points[0] <<" "<< setw(4) << points[1] << endl;
cout << endl << "Press any key..." << endl;
getch();
return 0;
}
Умопомрочительная смесь из С и С++, использование void* и пр. приемов запутывания противника и привлечения багов.
Потрясающе:
Код:
int compare( const void *arg1, const void *arg2 )
{
if(*(int *)arg1==*(int *)arg2)
{
if(*(int *)arg1==*(int *)arg2)
А вот это вообще перл:
Код:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
кто бы мог подумать, что это приращение указателя путем привода его к числовому типу увеличению на размер указателя, обратному приведению к типу указателя и разыменованию!
Если это "проще всего", то я даже боюсь за сложные решения. :D
ShadyMan, действительно, сетка криво-квадратная, но может быть и криво-прямоугольная, однако строково-столбцевая структура всегда сохраняется. Другими словами - это всегда сетка, а не беспорядочный набор точек.
Merlin, сейчас буду разбираться что делает qsort.
Merlin, сейчас буду разбираться что делает qsort.
[QUOTE=Green]<skipped>Если это "проще всего", то я даже боюсь за сложные решения. :D[/QUOTE]Green, я уже тебе отвечал, что твои фобии, это твои проблемы... :)
[QUOTE=Andreww]Merlin, сейчас буду разбираться что делает qsort.[/QUOTE]
Ниже есть еще версия использующая STL.
Щас Green на него рецензию напишет...:)
Ниже есть еще версия использующая STL.
Щас Green на него рецензию напишет...:)
Так, ребята, а ну не ссорьтесь, а то опять мою тему закроют =) Сорри за оффтоп.
[QUOTE=Мerlin]Ниже есть еще версия использующая STL.
Щас Green на него рецензию напишет...:)[/QUOTE]
на версию использующую через ж... STL я рецензию писать не буду, код дурной, но для задач новичка потянет.
Использование С и С++ вперемешку тоже обсуждать не буду. Понятно, что это у тебя стиль такой, типа хиппи в городе.
Ты мне объясни почему нельзя было функцию compare записать нормально, ну к примеру так:
Кстати, ты в курсе, что записть (*it).x можно сделать более читабельной: it->x
Щас Green на него рецензию напишет...:)[/QUOTE]
на версию использующую через ж... STL я рецензию писать не буду, код дурной, но для задач новичка потянет.
Использование С и С++ вперемешку тоже обсуждать не буду. Понятно, что это у тебя стиль такой, типа хиппи в городе.
Ты мне объясни почему нельзя было функцию compare записать нормально, ну к примеру так:
Код:
int compare(const void *arg1, const void *arg2)
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
Кстати, ты в курсе, что записть (*it).x можно сделать более читабельной: it->x
А теперь как бы действительно выглядел пример Мerlin с использованием STL (я не стал заводить другого контейнера, а оставил массив):
Код:
#include <iostream>
#include <algorithm>
using namespace std;
struct Point
{
int x, y;
};
Point points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
bool compare(const Point& point1, const Point& point2)
{
return (point1.x != point2.x) ? (point1.x < point2.x) : (point1.y > point2.y);
}
int main()
{
int size = sizeof(points)/sizeof(points[0]);
sort(points, points+size, compare);
for(int i = 0; i < size; i++)
cout << points.x <<" "<< points.y << endl;
return 0;
}
#include <algorithm>
using namespace std;
struct Point
{
int x, y;
};
Point points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
bool compare(const Point& point1, const Point& point2)
{
return (point1.x != point2.x) ? (point1.x < point2.x) : (point1.y > point2.y);
}
int main()
{
int size = sizeof(points)/sizeof(points[0]);
sort(points, points+size, compare);
for(int i = 0; i < size; i++)
cout << points.x <<" "<< points.y << endl;
return 0;
}
[QUOTE=Green]на версию использующую через ж... STL я рецензию писать не буду, код дурной, но для задач новичка потянет.
Использование С и С++ вперемешку тоже обсуждать не буду. Понятно, что это у тебя стиль такой, типа хиппи в городе.[/QUOTE]Чисто случайно недавно не ты бил себе грудь, что ты, в отличии от многих, не переходишь на обсуждение личности? :)
Использование С и С++ вперемешку тоже обсуждать не буду. Понятно, что это у тебя стиль такой, типа хиппи в городе.[/QUOTE]Чисто случайно недавно не ты бил себе грудь, что ты, в отличии от многих, не переходишь на обсуждение личности? :)
Цитата:
Ты мне объясни почему нельзя было функцию compare записать нормально, ну к примеру так:
Код:
int compare(const void *arg1, const void *arg2)
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
Кому как нравится. Вообще-то мне все равно, но мне кажется, что такие доп. конструкции программист использует, когда неуверен в коде.
Цитата:
А теперь как бы действительно выглядел пример Мerlin с использованием STL (я не стал заводить другого контейнера, а оставил массив):<skipped>
Первый ответ: На счет второго кода, ты меня не понял. imho его имеет смысл использовать, если набор точек динамически меняется. Типа заполняется set, и входе работы программы, то добавляются 2 точки, то удаляется точка итд. Твой код, это C++ версия первого кода.
Цитата:
А теперь как бы действительно выглядел пример Мerlin с использованием STL (я не стал заводить другого контейнера, а оставил массив):<skipped>
Второй ответ: А ты не можешь не переделывать мой код, а выкинуть что-то оригинальное? А то уже неинтересно. :)
[QUOTE=Мerlin]Чисто случайно недавно не ты бил себе грудь, что ты, в отличии от многих, не переходишь на обсуждение личности? :)
[/QUOTE]
А здесь не было ни слова о тебе... только о неаккуратном стиле.
[QUOTE=Мerlin]
Кому как нравится. Вообще-то мне все равно, но мне кажется, что такие доп. конструкции программист использует, когда неуверен в коде.
[/QUOTE]
Это не "доп. консрукции", а грамотное программирование или ты считаешь, что это аккуратнее и так пишут только уверенные в себе программисты:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
:D
[QUOTE=Мerlin]
Твой код, это C++ версия первого кода.
[/QUOTE]
Ах твой чудо-код это была С версия? :D
Ну-ну...
[QUOTE=Мerlin]
Второй ответ: А ты не можешь не переделывать мой код, а выкинуть что-то оригинальное? А то уже неинтересно.
[/QUOTE]
А кто тебе сказал, что я переделал твой код? Найди хоть что-то общее.
Если конечно формат qsort - это не твоё изобренение. :)
Ладно, все это мелочи. Ты мне объясни, чем ты руководствуешься, используя такие перлы:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.
[/QUOTE]
А здесь не было ни слова о тебе... только о неаккуратном стиле.
[QUOTE=Мerlin]
Кому как нравится. Вообще-то мне все равно, но мне кажется, что такие доп. конструкции программист использует, когда неуверен в коде.
[/QUOTE]
Это не "доп. консрукции", а грамотное программирование или ты считаешь, что это аккуратнее и так пишут только уверенные в себе программисты:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
:D
[QUOTE=Мerlin]
Твой код, это C++ версия первого кода.
[/QUOTE]
Ах твой чудо-код это была С версия? :D
Ну-ну...
[QUOTE=Мerlin]
Второй ответ: А ты не можешь не переделывать мой код, а выкинуть что-то оригинальное? А то уже неинтересно.
[/QUOTE]
А кто тебе сказал, что я переделал твой код? Найди хоть что-то общее.
Если конечно формат qsort - это не твоё изобренение. :)
Ладно, все это мелочи. Ты мне объясни, чем ты руководствуешься, используя такие перлы:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.
[quote=Green]
Ладно, все это мелочи. Ты мне объясни, чем ты руководствуешься, используя такие перлы:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.[/quote]
ИМХО, стеб. а ты на провокации поддаешся.
Ладно, все это мелочи. Ты мне объясни, чем ты руководствуешься, используя такие перлы:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.[/quote]
ИМХО, стеб. а ты на провокации поддаешся.
Да меня это развлекает.
Я тоже не могу поверить, что люди так пишут. :)
Я тоже не могу поверить, что люди так пишут. :)
[QUOTE=squirL]ИМХО, стеб. а ты на провокации поддаешся.[/QUOTE]
А может перед тем, как критиковать кого либо, ты сперва на свой код посмотришь? :) Код взят с http://forum.codenet.ru/showthread.php?goto=newpost&t=29576
Три вопроса.
1. Если например читается файл из 10 строк, и есть символ ":", во всех строках, кроме 1-й, тогда файл будет правильно обработан?
2. Выделяется память под line, командой malloc. Каким образом освободить этот память в конце программы?
3. Тебе не кажется, что не лучшая идея сперва выделить память и только после этого проверять, есть ли что туда писать? Ведь если например 3-я строка имеет вид:
#daemon:x:2:2:daemon:/sbin:
тогда для list[2] память будет выделяться дважды, и память выделенная первый раз, будет потеряна.
А может перед тем, как критиковать кого либо, ты сперва на свой код посмотришь? :) Код взят с http://forum.codenet.ru/showthread.php?goto=newpost&t=29576
Код:
#include <stdio.h>
int main()
{
FILE *fp;
char *line;
char *list[255];
line = (char*) malloc(255);
fp = fopen("/etc/passwd","r");
int i=0;
do
{
line = fgets(line, 255, fp);
strtok(line,":");
list= (char*) malloc(255);
if (line && (strncmp(line,"#",1))) strcpy(list[i++],line);
}
while (line);
fclose(fp);
}
int main()
{
FILE *fp;
char *line;
char *list[255];
line = (char*) malloc(255);
fp = fopen("/etc/passwd","r");
int i=0;
do
{
line = fgets(line, 255, fp);
strtok(line,":");
list= (char*) malloc(255);
if (line && (strncmp(line,"#",1))) strcpy(list[i++],line);
}
while (line);
fclose(fp);
}
1. Если например читается файл из 10 строк, и есть символ ":", во всех строках, кроме 1-й, тогда файл будет правильно обработан?
2. Выделяется память под line, командой malloc. Каким образом освободить этот память в конце программы?
3. Тебе не кажется, что не лучшая идея сперва выделить память и только после этого проверять, есть ли что туда писать? Ведь если например 3-я строка имеет вид:
#daemon:x:2:2:daemon:/sbin:
тогда для list[2] память будет выделяться дважды, и память выделенная первый раз, будет потеряна.
[QUOTE=Green]Ладно, все это мелочи. Ты мне объясни, чем ты руководствуешься, используя такие перлы:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.[/QUOTE]Здравым смыслом, в отличие от некоторых программистов С++, у которых здравого смысла заменяет Стандарт С++.
Прошлый раз ты пристал к коду, который был вырезан с MSDN. Теперь тебе вот эта команда не нравится. Я всего навсего хотел ответить на вопрос, как отсортировать массивы. Хочешь, сказать что приведенные мною коды для статического и динамического случая, сортируют массив в неправильном порядке? Или же вместо сортировки форматируют винт? Или же код настолько запутан, что не можно понять идею решения?
Пойми одно. Есть люди, которые отвечают на какой-то вопрос, только потому что вопрос кажется им интересным. И есть люди, которые ходят на форумы, чтоб самоутвердиться. Чтоб показать миру: смотрите, какие мы умные, какой красивый код мы умеем писать. Ну вот эти вторые, пусть тратят свое время на написание красивого кода. Лично мне даже той времени жалко, которого я трачу на этот спор.
Мимоходом, ты какое место занял, на чемпионате мира по красивому программному коду? :)
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Мне серьезно интересно.[/QUOTE]Здравым смыслом, в отличие от некоторых программистов С++, у которых здравого смысла заменяет Стандарт С++.
Прошлый раз ты пристал к коду, который был вырезан с MSDN. Теперь тебе вот эта команда не нравится. Я всего навсего хотел ответить на вопрос, как отсортировать массивы. Хочешь, сказать что приведенные мною коды для статического и динамического случая, сортируют массив в неправильном порядке? Или же вместо сортировки форматируют винт? Или же код настолько запутан, что не можно понять идею решения?
Пойми одно. Есть люди, которые отвечают на какой-то вопрос, только потому что вопрос кажется им интересным. И есть люди, которые ходят на форумы, чтоб самоутвердиться. Чтоб показать миру: смотрите, какие мы умные, какой красивый код мы умеем писать. Ну вот эти вторые, пусть тратят свое время на написание красивого кода. Лично мне даже той времени жалко, которого я трачу на этот спор.
Мимоходом, ты какое место занял, на чемпионате мира по красивому программному коду? :)
[quote=Мerlin]
}[/code]Три вопроса.
1. Если например читается файл из 10 строк, и есть символ ":", во всех строках, кроме 1-й, тогда файл будет правильно обработан?
2. Выделяется память под line, командой malloc. Каким образом освободить этот память в конце программы?
3. Тебе не кажется, что не лучшая идея сперва выделить память и только после этого проверять, есть ли что туда писать? Ведь если например 3-я строка имеет вид:
[/quote]
1. passwd имеет стандартную структуру.
2. никак. я это студенту оставил. так же и память выделяемая под list никак не освободится.
3. ужасная идея.
а где вы были - программисты? я долго и героически ждал, пока человеку кто либо поможет. потом взял справочник по языку и склепал свою корявую прогу. работает - работает. ну а студент имеет шанс ее улучшить, если додумается.
}[/code]Три вопроса.
1. Если например читается файл из 10 строк, и есть символ ":", во всех строках, кроме 1-й, тогда файл будет правильно обработан?
2. Выделяется память под line, командой malloc. Каким образом освободить этот память в конце программы?
3. Тебе не кажется, что не лучшая идея сперва выделить память и только после этого проверять, есть ли что туда писать? Ведь если например 3-я строка имеет вид:
[/quote]
1. passwd имеет стандартную структуру.
2. никак. я это студенту оставил. так же и память выделяемая под list никак не освободится.
3. ужасная идея.
а где вы были - программисты? я долго и героически ждал, пока человеку кто либо поможет. потом взял справочник по языку и склепал свою корявую прогу. работает - работает. ну а студент имеет шанс ее улучшить, если додумается.
Друзья, вы чего?! Andreww, ты проверял то, что написал Green? По-моему, он просто тупо отсортировал все точки по первой координате. Ты этого хотел? Я специально откомпилировал его пример и даже проверил в Paint'е, как эти точки будут расставлены. Они не идут в нужном порядке. Или я неправильно понял твоё условие:
[QUOTE=Andreww]первый элемент массива - это верхняя левая точка, второй элемент - вторая сверху точка в первом столбце. и так далее.[/QUOTE]
У меня получилось так: первые три точки идут, как надо, а четвертая вдруг неожиданно влазиет между первой и второй.
[QUOTE=Andreww]первый элемент массива - это верхняя левая точка, второй элемент - вторая сверху точка в первом столбце. и так далее.[/QUOTE]
У меня получилось так: первые три точки идут, как надо, а четвертая вдруг неожиданно влазиет между первой и второй.
Ой, ребята, ну вы нафлудили! Я уже запутался :-) Куча кода, не чтоб идейку словами подсказать...
ShadyMan, да, я тоже увидел что есть глюк -- точки сортируются только по первой координате. В общем ребята соревнуясь за красивостью кода забыли про условие... Бывает.
ShadyMan, да, я тоже увидел что есть глюк -- точки сортируются только по первой координате. В общем ребята соревнуясь за красивостью кода забыли про условие... Бывает.
Да, точки в прмере сортируются именно по одной координате, в случае совпадения координат сортируются по второй координате.
А разве ты не это имел в виду? Именно так происходит в твоем примере.
Тогда как именно должны сортироваться точки? Опиши алгоритм сортировки.
А разве ты не это имел в виду? Именно так происходит в твоем примере.
Тогда как именно должны сортироваться точки? Опиши алгоритм сортировки.
Да нет, Green, ты не понял. Точки должны сортироваться по второй координате не тогда, когда первые координаты равны, а в любом случае. То есть, и по первой и по второй. Только индекс столбца имеет больший приоритет.
На, Andreww, лови готовый код.
Только учти, я считал, что x индексирует столбцы, а y - строки. То есть, как в евклидовой системе координат. Кажется, в программировании принято наоборот: первая координата индексирует строки. Но если что - переделаешь.
На, Andreww, лови готовый код.
Код:
#include <windows.h>
#include <conio.h>
int compareX(const POINT *p1, const POINT *p2)
{
if (p1->x<p2->x) return -1;
return 1;
}
int compareY(const POINT *p1, const POINT *p2)
{
if (p1->y<p2->y) return -1;
return 1;
}
void sort_points(POINT *points, int iWidth, int iHeight)
{
int iCount=iWidth*iHeight;
qsort(points, iCount, sizeof(POINT), &compareX);
for (int i=0; i<iCount; i+=iHeight)
qsort(&points, iHeight, sizeof(POINT), &compareY);
for (int i=0; i<iCount; i++)
cprintf("%d %d\r\n", points.x, points.y);
cprintf("Press any key to end");
getch();
}
int main(void)
{
POINT points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
sort_points(points, 4, 4);
return 0;
}
#include <conio.h>
int compareX(const POINT *p1, const POINT *p2)
{
if (p1->x<p2->x) return -1;
return 1;
}
int compareY(const POINT *p1, const POINT *p2)
{
if (p1->y<p2->y) return -1;
return 1;
}
void sort_points(POINT *points, int iWidth, int iHeight)
{
int iCount=iWidth*iHeight;
qsort(points, iCount, sizeof(POINT), &compareX);
for (int i=0; i<iCount; i+=iHeight)
qsort(&points, iHeight, sizeof(POINT), &compareY);
for (int i=0; i<iCount; i++)
cprintf("%d %d\r\n", points.x, points.y);
cprintf("Press any key to end");
getch();
}
int main(void)
{
POINT points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
sort_points(points, 4, 4);
return 0;
}
Тогда на рисунке после первой точки должна идти пятая (IMHO)?
А может по расстоянию между ближайшими (кстати, классная бы задачка на оптимальное решение была бы)?
Но лучше, пусь автор топика ответит.
А может по расстоянию между ближайшими (кстати, классная бы задачка на оптимальное решение была бы)?
Но лучше, пусь автор топика ответит.
Для тех, кому впадлу скомпилировать мой код, показываю, что он выдаёт:
15 20
22 73
18 127
22 173
66 26
69 81
81 128
83 177
128 24
134 72
145 127
150 168
182 15
182 90
185 129
191 180
По-моему, это полностью удовлетворяет условию задачи.
15 20
22 73
18 127
22 173
66 26
69 81
81 128
83 177
128 24
134 72
145 127
150 168
182 15
182 90
185 129
191 180
По-моему, это полностью удовлетворяет условию задачи.
Хм... кажется, ShadyMan уловил смысл задачи.
А все же какое условие задачи?
Точки действительно всегда располагаются вертикальными группами с одинаковым колличеством?
А бывает, что точки из разный групп имеют одинаковую координату X ?
Как тогда быть в этом случае?
Например:
{1,4} {2,4}
{2,3} {3,3}
{2,2} {3,2}
{2,1} {3,1}
А все же какое условие задачи?
Точки действительно всегда располагаются вертикальными группами с одинаковым колличеством?
А бывает, что точки из разный групп имеют одинаковую координату X ?
Как тогда быть в этом случае?
Например:
{1,4} {2,4}
{2,3} {3,3}
{2,2} {3,2}
{2,1} {3,1}
Ребят, условие задачи сформулирую завтра бо уже сплю практически ;-)
Насчет этого:
[QUOTE=Green]Ты мне объясни почему нельзя было функцию compare записать нормально, ну к примеру так:
[/QUOTE]
я бы поспорил - дело вкуса, создавать ли дополнительные переменные и делать код более читабельным, или же оставить всё как есть и ускорить и сократить исполнимый код (хотя бы и незначительно... хотя бы даже теоретически :)) за счет того, что нет дополнительных переменных и лишних пересылок.
А вот
Да, ты прав, выглядит не очень профессионально. С первого взгляда сложновато сказать, что такое 4, лишь потом становится понятно, что это размер двойного слова и лучше бы его заменить...
[QUOTE=Green]Ты мне объясни почему нельзя было функцию compare записать нормально, ну к примеру так:
Код:
int compare(const void *arg1, const void *arg2)
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
{
const int* iArg1 = (const int*) arg1;
const int* iArg2 = (const int*) arg2;
if(*iArg1 == *iArg2)
return *(iArg2+1) - *(iArg1+1);
else
return *iArg1 - *iArg2;
}
[/QUOTE]
я бы поспорил - дело вкуса, создавать ли дополнительные переменные и делать код более читабельным, или же оставить всё как есть и ускорить и сократить исполнимый код (хотя бы и незначительно... хотя бы даже теоретически :)) за счет того, что нет дополнительных переменных и лишних пересылок.
А вот
Код:
return *(int *)((int)arg2+4) - *(int *)((int)arg1+4);
Да, ты прав, выглядит не очень профессионально. С первого взгляда сложновато сказать, что такое 4, лишь потом становится понятно, что это размер двойного слова и лучше бы его заменить...
Код:
1. return ((int*)arg2)[1] - ((int*)arg1)[1];
2. return *((int*)arg2+1) - *((int*)arg1+1);
или, на худой конец, 3. return *(int *)((int)arg2+sizeof(int)) - *(int *)((int)arg1+sizeof(int));
2. return *((int*)arg2+1) - *((int*)arg1+1);
или, на худой конец, 3. return *(int *)((int)arg2+sizeof(int)) - *(int *)((int)arg1+sizeof(int));
Рассказываю условие задачи. Есть 2 файла-картинки с точками. Я прохожу по первому файлу, нахожу координаты всех точек, потом прохожу по второму файлу и тоже нахожу координаты всех точек. Мой алгоритм поиска точек находит их в разбросанном порядке, то есть не подряд. А МНЕ НУЖНО затем отнять координаты точек из первого файла от координат точек со второго файла. А ДЛЯ ЭТОГО и нужно отсортировать два массива с точками чтобы из точки обозначенной на первой картинке красным кружком отнимать точку на второй картинке тоже обозначенную красным кружком (см. прикрепленный рисунок). Ну и так далее. Другими словами - установить соответствие между двумя массивами координат.
ShadyMan, спасибо, я сейчас пытаюсь понять как это работает. Но работает правильно, это факт.
ShadyMan, спасибо, я сейчас пытаюсь понять как это работает. Но работает правильно, это факт.
[QUOTE=Andreww]
ShadyMan, спасибо, я сейчас пытаюсь понять как это работает. Но работает правильно, это факт.[/QUOTE]
Гы :) что-то написали, и теперь пытаемся понять, как оно работает :) Надо в раздел Юмора!
ShadyMan, спасибо, я сейчас пытаюсь понять как это работает. Но работает правильно, это факт.[/QUOTE]
Гы :) что-то написали, и теперь пытаемся понять, как оно работает :) Надо в раздел Юмора!
ShadyMan, а вы в какой среде компилите? У меня что-то в билдере 5 ошибки вылазят:
[C++ Error] Unit1.cpp(19): E2034 Cannot convert 'int (*)(const tagPOINT *,const tagPOINT *)' to 'int (*)(const void *,const void *)'
[C++ Error] Unit1.cpp(19): E2342 Type mismatch in parameter '__fcmp' (wanted 'int (*)(const void *,const void *)', got 'int (*)(const tagPOINT *,const tagPOINT *)')
[C++ Error] Unit1.cpp(21): E2034 Cannot convert 'int (*)(const tagPOINT *,const tagPOINT *)' to 'int (*)(const void *,const void *)'
[C++ Error] Unit1.cpp(21): E2342 Type mismatch in parameter '__fcmp' (wanted 'int (*)(const void *,const void *)', got 'int (*)(const tagPOINT *,const tagPOINT *)')
[C++ Error] Unit1.cpp(19): E2034 Cannot convert 'int (*)(const tagPOINT *,const tagPOINT *)' to 'int (*)(const void *,const void *)'
[C++ Error] Unit1.cpp(19): E2342 Type mismatch in parameter '__fcmp' (wanted 'int (*)(const void *,const void *)', got 'int (*)(const tagPOINT *,const tagPOINT *)')
[C++ Error] Unit1.cpp(21): E2034 Cannot convert 'int (*)(const tagPOINT *,const tagPOINT *)' to 'int (*)(const void *,const void *)'
[C++ Error] Unit1.cpp(21): E2342 Type mismatch in parameter '__fcmp' (wanted 'int (*)(const void *,const void *)', got 'int (*)(const tagPOINT *,const tagPOINT *)')
[QUOTE=Andreww]ShadyMan, а вы в какой среде компилите? У меня что-то в билдере 5 ошибки вылазят:
[/QUOTE]Нужно заменить ф-ии CompareX/Y на
[/QUOTE]Нужно заменить ф-ии CompareX/Y на
Код:
int compareX(const void *p1, const void *p2)
{
return ((POINT *)p1)->x-((POINT *)p2)->x;
}
int compareY(const void *p1, const void *p2)
{
return ((POINT *)p1)->y-((POINT *)p2)->y;
}
{
return ((POINT *)p1)->x-((POINT *)p2)->x;
}
int compareY(const void *p1, const void *p2)
{
return ((POINT *)p1)->y-((POINT *)p2)->y;
}
[QUOTE=Andreww]ShadyMan, а вы в какой среде компилите?[/QUOTE]
Я компилирую в lcc, а он, действительно, не так чувствителен к подобным вещам, как Builder. Merlin совершенно прав: так и выглядит лучше, и с Builder'ом никаких проблем. Да, и ещё: в моей 5 версии Builder'a конструкция типа for(int i; ...) не прокатывает. Компилятор не понимает объявления переменных внутри for. С учётом всего этого предлагаю переработанный вариант специально для Builder'a.
Я компилирую в lcc, а он, действительно, не так чувствителен к подобным вещам, как Builder. Merlin совершенно прав: так и выглядит лучше, и с Builder'ом никаких проблем. Да, и ещё: в моей 5 версии Builder'a конструкция типа for(int i; ...) не прокатывает. Компилятор не понимает объявления переменных внутри for. С учётом всего этого предлагаю переработанный вариант специально для Builder'a.
Код:
#pragma hdrstop
#include <windows.h>
#include <conio.h>
int compareX(const void *p1, const void *p2)
{
return ((POINT *)p1)->x-((POINT *)p2)->x;
}
int compareY(const void *p1, const void *p2)
{
return ((POINT *)p1)->y-((POINT *)p2)->y;
}
void sort_points(POINT *points, int iWidth, int iHeight)
{
int iCount=iWidth*iHeight, i;
qsort(points, iCount, sizeof(POINT), &compareX);
for (i=0; i<iCount; i+=iHeight)
qsort(&points, iHeight, sizeof(POINT), &compareY);
for (i=0; i<iCount; i++)
cprintf("%d %d\r\n", points.x, points.y);
cprintf("Press any key to end");
getch();
}
int main(void)
{
POINT points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
sort_points(points, 4, 4);
return 0;
}
#include <windows.h>
#include <conio.h>
int compareX(const void *p1, const void *p2)
{
return ((POINT *)p1)->x-((POINT *)p2)->x;
}
int compareY(const void *p1, const void *p2)
{
return ((POINT *)p1)->y-((POINT *)p2)->y;
}
void sort_points(POINT *points, int iWidth, int iHeight)
{
int iCount=iWidth*iHeight, i;
qsort(points, iCount, sizeof(POINT), &compareX);
for (i=0; i<iCount; i+=iHeight)
qsort(&points, iHeight, sizeof(POINT), &compareY);
for (i=0; i<iCount; i++)
cprintf("%d %d\r\n", points.x, points.y);
cprintf("Press any key to end");
getch();
}
int main(void)
{
POINT points[] =
{
{128, 24}, { 15, 20}, { 66, 26}, { 69, 81},
{22, 73}, {191, 180}, {134, 72}, {145, 127},
{182, 90}, { 18, 127}, { 81, 128}, {150, 168},
{185, 129}, { 22, 173}, {182, 15}, { 83, 177}
};
sort_points(points, 4, 4);
return 0;
}
Спасибо за помощь!
А как это в билдере 5 не прокатывает конструкция for (int i; ...)? Я всегда только так и пишу!
Кстати, вот еще вопрос на подумать - если размерность массива точек заранее не известна? То есть их не обязательно 4х4, а может быть и 10х15... Наверное не просто будет восстановить размерность массива исходя из набора точек?
А как это в билдере 5 не прокатывает конструкция for (int i; ...)? Я всегда только так и пишу!
Кстати, вот еще вопрос на подумать - если размерность массива точек заранее не известна? То есть их не обязательно 4х4, а может быть и 10х15... Наверное не просто будет восстановить размерность массива исходя из набора точек?
[QUOTE=Andreww]А как это в билдере 5 не прокатывает конструкция for (int i; ...)? Я всегда только так и пишу![/QUOTE]
В проектах С++ прокатывает, а в С (когда создаёшь новый консольный проект и выбираешь source type - C) - нет.
[QUOTE=Andreww]Кстати, вот еще вопрос на подумать - если размерность массива точек заранее не известна?[/QUOTE] А это вопрос абстрактный или насущный?
В проектах С++ прокатывает, а в С (когда создаёшь новый консольный проект и выбираешь source type - C) - нет.
[QUOTE=Andreww]Кстати, вот еще вопрос на подумать - если размерность массива точек заранее не известна?[/QUOTE] А это вопрос абстрактный или насущный?
[quote=ShadyMan]В проектах С++ прокатывает, а в С (когда создаёшь новый консольный проект и выбираешь source type - C) - нет.
[/quote]
естественно. потому что объявление переменных по ходу программы это фича С++. gcc, например, на такое скажет
[/quote]
естественно. потому что объявление переменных по ходу программы это фича С++. gcc, например, на такое скажет
Цитата:
error: 'for' loop initial declaration used outside C99 mode
ShadyMan, вопрос насущный. В принципе у меня при выполнении программы показывается картинка обрабатываемого файла, так что можно заставить пользователя самому посчитать кол-во строк и столбцов и ввести в программу, но это уже человеческий фактор (может ошибиться), и лишняя морока со стороны юзера. Если б программа могла сама анализировать массив координат точек и делать вывод сколько строк в картинке и сколько столбцов, то это было б отлично. Но я думал над этим вопросом..... по моему никак.....
Можно определить. Нужно наложить сетку на точки. Т.е. разделить столбцы и строки прямыми линиями. Одна проблема, что набор точек может быть неоднозначным. Напр. на набор из примера можно наложить сетку 8*2 и 4*4. Но если из двух размерностей выбирать тот, который имеет меньшую среднюю ширину столбцов и высоту строк, тогда и эту проблему можно решить.
[QUOTE=squirL]естественно. потому что объявление переменных по ходу программы это фича С++. gcc, например, на такое скажет[/QUOTE]
А вот и нет. Я уже писал, что использую lcc - компилятор языка С - без всяких плюсов, и там это работает. Другое дело, может, это нетипично для С, но и что это прерогатива С++ - тоже сказать нельзя.
А вот и нет. Я уже писал, что использую lcc - компилятор языка С - без всяких плюсов, и там это работает. Другое дело, может, это нетипично для С, но и что это прерогатива С++ - тоже сказать нельзя.
это может означать, что lcc не соответствует стандарту языка С. точно так же Borland C++ (если я правильно помню) позволял определять подобную конструкцию. я начинал с С++, а С было после. и вот, приучившись и там и там использовать такую конструкцию, я долго сражался с gcc - одни версии признавали объявление переменных по ходу программы, а более старшие - нет... так что в борьбе за частоту языка Green не так уж и не прав ;)
А ты чувачок, я смотрю, нагловатый:D :D :D . Хочешь, чтоб за тебя всю программу написали?
Нет, если серьёзно, задача интересная. Я над всем этим хорошо подумал и вот что я тебе скажу. Твою картинку на строки и столбцы разбивает человеческое восприятие. Фактически, происходит это по законам статистики: точки со сходными признаками объединяются в группы. Хороший математик или статист решит тебе эту задачу в 2 счёта. Но статистика - на то и статистика, что оперирует большими совокупностями элементов, а это, как я понял, не твой случай. Вероятность ошибочного распределения точек столь же велика, сколь мала твоя совокупность. О 100-процентно правильном решении не может быть и речи. С другой стороны, зачем ты вообще придумал сортировать точки по строкам и столбцам? Если у тебя 2 файла и тебе нужно установить какая точка из первого файла соответствует какой во втором файле, то и надо искать эти соответствия. То есть, для каждой точки первого файла необходимо вычислить, какая из точек второго наиболее близка к ней по координатам. И всё.
Нет, если серьёзно, задача интересная. Я над всем этим хорошо подумал и вот что я тебе скажу. Твою картинку на строки и столбцы разбивает человеческое восприятие. Фактически, происходит это по законам статистики: точки со сходными признаками объединяются в группы. Хороший математик или статист решит тебе эту задачу в 2 счёта. Но статистика - на то и статистика, что оперирует большими совокупностями элементов, а это, как я понял, не твой случай. Вероятность ошибочного распределения точек столь же велика, сколь мала твоя совокупность. О 100-процентно правильном решении не может быть и речи. С другой стороны, зачем ты вообще придумал сортировать точки по строкам и столбцам? Если у тебя 2 файла и тебе нужно установить какая точка из первого файла соответствует какой во втором файле, то и надо искать эти соответствия. То есть, для каждой точки первого файла необходимо вычислить, какая из точек второго наиболее близка к ней по координатам. И всё.
Хе, хе, в том то и дело, что если б можно было наложить сетку то эта софтинка была б уже давно написана, а так реальность такова что пятна на картинке иногда получаются сильно сильно разбросанными, поэтому мне пришлось находить их хитрыми способами -- отсюда и "кривые" массивы которые требуют хитрой сортировки....
А выискивать наиболее близкие точки это не есть правильно, так как одна из картинок может "разьехаться" относительно второй и в этом случае нужно именно сортировать, эээээ понятно почему? че-то не могу доходчиво обьяснить....
Всю программу не надо :-) тут просто такая софтина что у меня уже мозги набекрень, близимся к финалу, поэтому уже мозговарение плохое :-)
А выискивать наиболее близкие точки это не есть правильно, так как одна из картинок может "разьехаться" относительно второй и в этом случае нужно именно сортировать, эээээ понятно почему? че-то не могу доходчиво обьяснить....
Всю программу не надо :-) тут просто такая софтина что у меня уже мозги набекрень, близимся к финалу, поэтому уже мозговарение плохое :-)
[QUOTE=ShadyMan]...Если у тебя 2 файла и тебе нужно установить какая точка из первого файла соответствует какой во втором файле, то и надо искать эти соответствия. То есть, для каждой точки первого файла необходимо вычислить, какая из точек второго наиболее близка к ней по координатам. И всё.[/QUOTE]Если для одной точки первого файла найдется 3 равноудаленных точек второго файла, тогда которую из этих трех выбрать?