Задача про хорды - Помощь студентам

Assasin92 · 25.03.2012, 12:31

Здравствуйте. Помогите пожалуйста с алгоритмом для решения следующей задачи:

Цитата:

На окружности расположено 2*n точек, пронумерованных от 1 до 2*n. Точки с номерами a_i, b_i соединены i-й хордой, причём каждая точка является концом ровно одной хорды. Необходимо найти количество пересекающихся пар хорд.

Я могу сделать только перебором, но в худшем случае, что я смог придумать, перебор работает за 8-9 сек, а надо уложиться в 2 сек.

vova_ · 25.03.2012, 14:30

Цитата:

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

На окружности расположено 2*n точек

каким образом задаютца положения точек
насколько я понял точьки пронумерованы по ходу окружности и как входные данные мы имеем пары точек пренадлежащих к одной хорде
1 4
2 5
3 6

и какого порядка n ?

Vago · 25.03.2012, 15:13

Цитата:

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

Я могу сделать только перебором

А как её решать-то БЕЗ перебора?! Другое дело, что перебор перебору - рознь...

Цитата:

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

в худшем случае, что я смог придумать, перебор работает за 8-9 сек, а надо уложиться в 2 сек.

Э-э... Простите... Это что, БЕЙСИК на Электронике БК 0010?..

8 секунд на задачу дискретной математики сложности O(n^2)?!..

vova_ · 25.03.2012, 15:34

Цитата:

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

А как её решать-то БЕЗ перебора?! Другое дело, что перебор перебору - рознь...

да у меня был случай как правильный перебор давал результат за 5-6 секунд
а не правельный по моим оценкам требовал 5 лет

Assasin92 · 25.03.2012, 15:57

Цитата:

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

каким образом задаютца положения точек
насколько я понял точьки пронумерованы по ходу окружности и как входные данные мы имеем пары точек пренадлежащих к одной хорде
1 4
2 5
3 6

и какого порядка n ?

Да, входные данные задаются именно так. 1 <= n <= 10^5.

Цитата:

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

А как её решать-то БЕЗ перебора?! Другое дело, что перебор перебору - рознь...

Я использовал прямой перебор: проверял каждую точку из первого столбца, смотрел, с какой точкой она соединена и проходил все точки между ними, проверяя условие пересечения. Надо действовать хитрее...

Цитата:

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

Э-э... Простите... Это что, БЕЙСИК на Электронике БК 0010?..

8 секунд на задачу дискретной математики сложности O(n^2)?!..

Я же сказал, что в худшем случае, который я смог придумать. Правда я не сказал, что n <= 10^5.

Vago · 25.03.2012, 16:43

Цитата:

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

Я же сказал, что в худшем случае, который я смог придумать. Правда я не сказал, что n <= 10^5.

Ну так выложил бы сюда то, что смог придумать. Иначе с чем сравнивать-то?..

Assasin92 · 25.03.2012, 18:32

Код, который должен решать задачу:

Код:

#include <iostream>
#include <fstream>

struct Dots {
	int first, second, numOfIntersections;
	Dots* next;
};
Dots *data = new Dots();
int count = 0, numOfChords;
void getData() {
	std::ifstream in("chords.in");
	Dots *temp = data;
	in >> numOfChords >> data->first >> data->second;
	--numOfChords;
	while(!in.eof())
	{
		temp = temp->next = new Dots();
		in >> temp->first >> temp->second;
	}
	in.close();
}
void check() {
	Dots *temp;
	for(int i = 0, difference; i < numOfChords; ++i)
	{
		difference = data->second - data->first - 1;
		if (difference == 1)
			goto skip;
		temp = data->next;
		for(int j = 0; j <= difference && data->numOfIntersections != difference; ++j)
			if(temp->first < data->second && temp->second > data->second)
			{
				++data->numOfIntersections;
				++temp->numOfIntersections;
				++count;
				temp = temp->next;
			}
skip:
		data = data->next;
	}
}

int main() {
	getData();
	check();
//	std::ofstream out("chords.out");
//	out << count;
//	out.close();
	return 0;
}

Код для генерации "худшего варианта"(писал давно, но то, что не закомментировано, должно генерировать именно худший случай. Если это не так, могу выложить txt для 3-4 случаев, вроде остались):

Код:

#include <iostream>
#include <fstream>

int main() {
    int max = 100000;
    std::ofstream /*out1("chords.in"), out2("chords2.in"), out3("chords3.in"), */out4("chords4.in");
//    out1 << max << std::endl;
//    out2 << max << std::endl;
//    out3 << max / 2 << std::endl;
      out4 << max << std::endl;
    for (int i = 1; i <= max; ++i) {
//        if (i % 2 == 1)
//        {
//            out1 << i << ' ' << (i + 1) << std::endl;
//            out3 << i << ' ' << (2 * i) << std::endl;
//        }
//        out2 << i << ' ' << (i + max) << std::endl;
        //if (i % 4 == 1 || i % 4 == 2)
          out4 << i << ' ' << i + max << std::endl;
    }
    return 0;
}

Задачу надо решить не за O (n^2), а за O (n * log(n)) хотя бы.

Vago · 25.03.2012, 22:34

Код:

#include <iostream>
#include <fstream>
#include <time.h>


struct Dots {
   int first, second ; //, numOfIntersections ;
   Dots* next ;
} ;


const unsigned int N = 80000 ;
Dots allChords[2*N] ;  
Dots *data ; 
char* cFileNm = "chords4.in" ;
int   numOfChords ;


int BuildAllChords( int nPoints ) {

   std::ofstream /*out1("chords.in"), out2("chords2.in"), out3("chords3.in"), */out4( cFileNm ) ;
   out4 << nPoints << std::endl;
   for (int i = 1; i <= nPoints/2; ++i) 
       out4 << i << ' ' << i + nPoints/2 << std::endl;

   return 0;

}


void getData() {

   std::ifstream in( cFileNm ) ;
   int   i, nPoints ;

   in >> nPoints ;
   numOfChords = nPoints / 2 ;
   
   for ( i = 0; i < numOfChords; i++ ) 
      in >> allChords[i].first >> allChords[i].second ;

   in.close() ;

}


void BuildList( int numOfChords ) {

   int   i ;
   Dots* temp ;

   data = new Dots() ;
   data->first = allChords[0].first ;
   data->second = allChords[0].second ;
   
   temp = data;
   for ( i = 1; i < numOfChords; i++ ) {
      temp = temp->next = new Dots() ;
      temp->first = allChords[i].first ;
      temp->second = allChords[i].second ;
   }
   temp->next = data ;

}


unsigned int checkAssasin92( bool isList  ) {

   Dots* temp ;
   int   count = 0, 
         difference, i, j, k ;

   if ( isList ) {
      for ( i = 0; i < numOfChords; ++i) {
         difference = data->second - data->first - 1;
         if (difference > 1) {
            temp = data->next;
//            for(int j = 1; j <= difference && data->numOfIntersections != difference; ++j) {
            for ( j = 1; j <= difference; ++j) {
               if ( temp->first < data->second && temp->second > data->second ) {
//				      ++data->numOfIntersections;
//				      ++temp->numOfIntersections;
				      ++count;
               }
               temp = temp->next;
            }
         } 
         data = data->next;
      }
      for ( i = 0; i < numOfChords; i++ ) {
         temp = data ;
         data = data->next ;
         delete temp ;
      }
   } else {
      for ( i = 0; i < numOfChords; ++i ) {
         difference = allChords[i].second - allChords[i].first - 1 ;
         if ( difference > 1 ) {
            k = i+1 ;
            for ( j = 1; j <= difference; ++j ) {
               if ( allChords[k].first < allChords[i].second && 
                    allChords[k].second > allChords[i].second ) 
                  ++count ;
               ++k ;
            }
         } 
      }
   }

   return count ;

}


unsigned int CheckVago() {
	
   int   count = 0 ,
         i, j,
         ptEnd0 ;
   
   for ( i = 0; i < numOfChords-1; ++i ) {
      ptEnd0 = allChords[i].second ;
      for ( j = i+1; j < numOfChords; ++j ) {
         if ( ptEnd0 < allChords[j].first || ptEnd0 > allChords[j].second )
            continue ;
         ++count ;
      }
   }

   return count ;

}


int main() {

   unsigned int   count ;
   long  tBefore, tAfter ;

   BuildAllChords( 2*N ) ;
	getData() ;

   BuildList( N ) ;

   time( &tBefore ) ;
   count = checkAssasin92( true ) ;
   time( &tAfter ) ;
   std::cout << " Assasin92 (list):" << std::endl ;
   std::cout << " t = " << tAfter - tBefore << " (s)" << std::endl ;
   std::cout << " N crossings = " << count << std::endl << std::endl ;

   time( &tBefore ) ;
   count = checkAssasin92( false ) ;
   time( &tAfter ) ;
   std::cout << " Assasin92 (array):" << std::endl ;
   std::cout << " t = " << tAfter - tBefore << " (s)" << std::endl ;
   std::cout << " N crossings = " << count << std::endl << std::endl ;
   
   time( &tBefore ) ;
   count = CheckVago() ;
   time( &tAfter ) ;
   std::cout << " Vago:" << std::endl ;
   std::cout << " t = " << tAfter - tBefore << " (s)" << std::endl ;
   std::cout << " N crossings = " << count << std::endl << std::endl ;

   std::ofstream out("chords.out");
   out << count ;
   out.close();

   return 0 ;

}

120325.jpg

1. Двукратное сокращение времени, благодаря переходу от списка к массиву, и ещё двукратное - после небольшого изменения алгоритма (хотя сложность, по-прежнему O(n^2)). Вот Вам вожделенные 2 секунды вместо 8.

2. Либо я чего-то не понял, либо у Вас data->numOfIntersections первый раз используется непроинициализированным, поэтому я эту доп. проверку у Вас в Варианте I просто выбросил

3. Написал new() - напиши delete()! Когда ж в вас преподаватели это вобьют наконец?!..

4. Всё это работает только если для каждой хорды меньший номер вершины стоит первым, а больший - вторым. Для файла

Код:

4
4 2
3 1

нужно немного усложнить логику.

5. Про O(n*log(n)) - это надо подумать...

Assasin92 · 26.03.2012, 16:59

Спасибо, постараюсь сегодня просмотреть код.

Цитата:

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

3. Написал new() - напиши delete()! Когда ж в вас преподаватели это вобьют наконец?!..

Ну... Преподаватели вбили ещё год назад, но сейчас я посчитал это ненужным. Прога-то в данном случае работает только однажды на одном тесте.

Цитата:

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

4. Всё это работает только если для каждой хорды меньший номер вершины стоит первым, а больший - вторым. Для файла

Код:

4
4 2
3 1

нужно немного усложнить логику.

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

Цитата:

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

5. Про O(n*log(n)) - это надо подумать...

Мне вот посоветовали использовать дерево отрезков. Только я не понимаю, как её здесь использовать. Если не ошибаюсь, эта структура позволяет искать минимум из элементов с индексами из отрезка [left, right], а также модифицировать i-й элемент за O (log(n)).

Assasin92 · 28.03.2012, 19:04

Цитата:

Похоже, проц у меня значительно слабее(Core 2 Duo E5300):

В тестирующей системе процессор будет ещё хуже... Так что прямой перебор хорд по порядку и проверка пересечений её с другими отпадает...

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Задача про рекурсию	NIKI18	Общие вопросы C/C++	1	19.12.2011 20:35
Задача про списки	Алекс12345	Паскаль, Turbo Pascal, PascalABC.NET	2	20.08.2011 19:33
Задача про банк.....	Васильева Зинаида	Помощь студентам	3	07.11.2010 13:05
задача про муху	DarkMage	Общие вопросы C/C++	1	14.09.2010 20:59