Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2010-01-30 11:35:43

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Как делать задачи?

60 балов CD:

Код:

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int cnt=0;
    int temp,prev=-1;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        if(i==0) cnt++;
        else if(prev!=temp) cnt++;
        prev=temp;
        
    }
         cout<<cnt-prev<<endl;
    return 0;
}

как я делал
ДВД:
1-е сделать вектор отрезков рабочего времни
2-е разбил его нерабочим временем - у нас получилось некое количество откезков который можно использовать
3-е разбил наши рабочие отрезки так: у каждого отверза три параметра - начало, конец, тип(4q,2q,q) и жадным алгоритмом каждый отрезок разбиваю на мелкие по 4q потом что останеться по 2q и потом по 3q
4-е если наших отрезков меньше чем нужно дисков, то сначала ищем и разбиваем отрезки 4q по 2q - так как было качество 3 станет 2+2=4 и увелисится диск, если разбиений 4q не хватает, то разбиваем 2q по q , нужно сначала рахбивать 4q так как 2+2=4, 2q: 1+1=2, тоесть качество будет больше
5-е подсчет, сначала считаем все там где 4q и удаляем эти отрезки, если дисков еше нехватает то считаем 2q и потом просто q
ну вот это решение должно проходить, но я криво закодил smile

Case:
если сделать матрицу связи група/люди
например:
вверху група, с боку люди
   1234
1 х___
2 х__х
3 _хх_
4 ххх_
5 хххх
6 ___х

"х"-связть есть, "_" - нету
и нам нужно использую только точки "х"
найти расстановку шахматных тур(ладья) в количестве равным количеству груп
а остальных людей определить в любую групу к которой они пренадлежат - я делал рекурсия с откатом

Woods я незнаю как делать sad чета неувидил sad
Border сейчас сделаю рисунок и напишу

Поза форумом

 

#2 2010-01-30 12:15:24

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Как делать задачи?

http://avoreg.ru/pic_s/a5f4cfcd46c7b8dacaee5dd04dbdac03.jpg
вот картинка для бордера
пусть угол гамма = G, бетта = B, Альфа - L
мы можем узнать угол L через треугольник O1O2 и точки внизу, потом берем арккосинус/арктангенс пот у нас есть угол L
чтобы найти угол B = arccos((R1-R2)/O1O2);
угол G = PI-L-G;
и теперь у нас есть угол G и R круга, находим через косинус/синус угла смещенние по X и по Y
для кольца с меньшим радиусом
X=r*cos(L);
Y=r*sin(L);

ВОт это теория, в задаче же я так и несмог закодить так это то что смещение по X Y для обоих окружнойстей может быть с разными знаками в зависимости от их взаимного расположение, тоесть толи как на рисунке, толи с больши радиусом внизу, с меньшим вверху

для каждый хвух колец мы знаем 2 касательный - сверху и снизу,
нужно закодить также определение какую касательную брать - нужно брать или все внутринии или все внешние
потом строим выпуклую оболочку:
берем три круг находим от двух из них касетльные к третему, получиться 2 отрезка - делаем из них прямую, находим точку пересечение и считаем угол который они делают, и по этому углу строим выпуклую оболочку

есть еше один вариант - для каждой касательный проверять чтобы ВСЕ остальный окружности лежали от нее с другой стороны , если так и есть то это будет какаято крайняя, если касательная пересекает хотябы одну из других окружностей или какихто 2 центра окружностей лежат с двух сторон - брать нельзя

вот так я хотел кодить, но всетаки не закодил, так как идея пришла только дня два назад и времени не хватало(учеба+подготовка к ЗНО...)
если есть варианты по проще  и будут работать с такойже точностью как и этот с удовольствием выслушаю

кстати думал еше над одним способом - разбить каждый круг на набор точек и строить по ним, но я так и не смог достигнуть нужной точности и приемлемого времени выполнения!

Відредаговано Cris (2010-01-30 12:16:02)

Поза форумом

 

#3 2010-01-30 12:22:28

alexo
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 18

Re: Как делать задачи?

ага, бордер и двд сделал также, но время неприемлимо 0.05 сек и получил за них 0 баллов=))

Поза форумом

 

#4 2010-01-30 12:48:46

Vinnie
Новий користувач
Зареєстрований: 2010-01-07
Повідомлень: 9

Re: Как делать задачи?

CD:

Код:

#include <iostream>
using namespace std;

int main()
{
   int N, k = 0, l, m;
   cin >> N >> l;
   while (--N) {
      cin >> m;
      if (m != l) {
         ++k;
         l = m;
      }
   }
   if (!l)
      ++k;
   cout << k;
   return 0;
}

Case:
Поиск полного паросочетания в двудольном графе.
(Алгоритм Хопкрофта-Карпа)
Border:
геометрия

Відредаговано Vinnie (2010-01-30 12:49:20)

Поза форумом

 

#5 2010-01-30 14:33:43

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Как делать задачи?

как Woods делать?

Поза форумом

 

#6 2010-01-30 16:05:28

zasqzasq
Новий користувач
Зареєстрований: 2009-11-05
Повідомлень: 11

Re: Как делать задачи?

я точно знаю, що в woods якщо нема обмеженнь(s=0) то кількість перестановок=k^(2*n)

Поза форумом

 

#7 2010-01-30 16:27:45

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Как делать задачи?

Там  використовуються наступні співвіднощення:
F(i,K1,K2) - кількість можливих заповнень перших і стовпчиків таблиці так, що в і-тому знаходяться дерева типів К1 і К2.
F(1,K1,K2)=
1).1 якщо пара (К1 К2) дозволена
2).0 інакше
F(i,K1,K2),i>1 = sum(F(i-1,K3,K4) : ( K1 K3) (K2 K4) дозволені)
складність O(N*K^4)

Відредаговано MAXXX (2010-01-30 16:28:38)


ICQ 426287475

Поза форумом

 

#8 2010-01-30 16:30:30

Eol
Новий користувач
Зареєстрований: 2009-11-08
Повідомлень: 5

Re: Как делать задачи?

ну, woods - динамика по краю. Заводим двумерный массив a[n, i] - кол-во расстановок поля 2*N и последней маской i (i - если перегнать в K-ричную систему счисления, то мы получим две цифры - это и будут два типа деревьев). Переход от a[n] к a[n+1] - это просто сопоставление всех масок.
Вот мой код (60 баллов):

Код:

const MODULE = 2010;                                       
var N, K : longint;                                        
    S : longint;                                           
    i, j : longint;                                        
    a, b : longint;                                        
    pool : array[1..5, 1..5] of boolean;                   
    compare : array[0..24, 0..24] of boolean;              
    dyn : array[1..100, 0..25] of longint;                 

procedure run(cpos : longint);
  var m1, m2 : longint;       
begin                         
  for m1:=0 to sqr(K)-1 do    
    for m2:=0 to sqr(K)-1 do  
      if compare[m1, m2] then 
        dyn[cpos, m2]:=(dyn[cpos, m2] + dyn[cpos-1, m1]) mod MODULE;
end;                                                                

begin
  fillchar(pool, sizeof(pool), true);
  fillchar(compare, sizeof(compare), false);
  fillchar(dyn, sizeof(dyn), 0);            
  {read}                                    
  read(N, K);                               
  read(S);                                  
  for i:=1 to S do begin                    
    read(a, b);                             
    pool[a, b]:=false;                      
    pool[b, a]:=false;                      
  end;                                      
  {precalc}                                 
  for i:=1 to K do                          
    for j:=1 to K do                        
        for a:=1 to K do
          for b:=1 to K do begin
            compare[(i-1)*K+j-1, (a-1)*K+b-1]:=(pool[a, b])and(pool[a, i])and(pool[b, j])and(pool[i, j]);
            compare[(a-1)*K+b-1, (i-1)*K+j-1]:=compare[(i-1)*K+j-1, (a-1)*K+b-1];
          end;
  {running}
  for i:=1 to K do
    for j:=1 to K do
      if pool[i, j] then
        inc(dyn[1, (i-1)*K+j-1]);
  for i:=2 to N do
    run(i);
  {write}
  s:=0;
  for i:=0 to sqr(K)-1 do
    s:=(s+dyn[N, i]) mod MODULE;
  writeln(s);
end.

Поза форумом

 

#9 2010-01-30 19:29:06

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

Eol написав:

ну, woods - динамика по краю. Заводим двумерный массив a[n, i] - кол-во расстановок поля 2*N и последней маской i (i - если перегнать в K-ричную систему счисления, то мы получим две цифры - это и будут два типа деревьев). Переход от a[n] к a[n+1] - это просто сопоставление всех масок.

Можно пожалуйста ссылку где об этом методе подробно расказывается.
А то я решал через матрицы. По ресурсам получилось намного эффективнее.

Поза форумом

 

#10 2010-01-30 20:07:55

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Как делать задачи?

pilya написав:

Eol написав:

ну, woods - динамика по краю. Заводим двумерный массив a[n, i] - кол-во расстановок поля 2*N и последней маской i (i - если перегнать в K-ричную систему счисления, то мы получим две цифры - это и будут два типа деревьев). Переход от a[n] к a[n+1] - это просто сопоставление всех масок.

Можно пожалуйста ссылку где об этом методе подробно расказывается.
А то я решал через матрицы. По ресурсам получилось намного эффективнее.

На самом деле, матрицами в таких случаях не всегда выгодно делать. К примеру, если доска была бы 4*N, то динамика, описанная выше прошла бы, а решение с матрицами - вряд ли, потому что его сложность O(logN*C^3), где C - количество допустимых "профилей". Зато, если бы доска была 2*10^9, тогда наоборот, решение матрицами проходило бы, а такое - нет.
Хотя странно, что на 3 туре ограничение на размер доски всего 2*100. Мне кажется, было бы интереснее, если бы доса была 8*100 или 3*10^9. В обоих случаях описанная выше динамика не проходила бы.

Поза форумом

 

#11 2010-01-30 20:30:31

n1ce
Новий користувач
Зареєстрований: 2009-11-28
Повідомлень: 19

Re: Как делать задачи?

Задачу woods решал по аналогии с одной интересной задачей Киевской олимпиады прошлого года.

Завдання
Обчислити остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4 на N, при яких вони не атакують один одного.

Вхідні дані
В єдиному рядку вхідного файлу записано два натуральних числа — довжина дошки N (2 ≤ N ≤ 109) і дільник P (2 ≤ P ≤ 109).

Вихідні дані
Єдиний рядок вихідного файлу має містити одне ціле число — остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4 на N, при яких вони не атакують один одного.

Розв'язання:
Рівень 1. Можна здійснити повний перебір усіх варіантів розміщень коней з подальшою перевіркою коректності розташування. Для дошки 4×N будемо мати 2^(4N) таких розміщень. Час на перевірку коректності розташування пропорційний N. Тому таке розв’язання виконує кількість операцій, що  пропорційна N∙2^N. Таким чином можна вирахувати значення кількостей для N від 2 до 7 за час туру олімпіади, задати ці кількості сталими у коді програми і для вказанихх N виводити остачу від ділення на Р попередньо обчислені  кількості розташувань. Таке розв’язання набирає 15% балів.
Рівень 2. Знаючи кількість розташувань на дошці 4×(N – 1) для кожних можливих двох останніх стовпчиків, ми можемо досить швидко визначити такі кількості вже для дошки 4×N. Існує 28 варіантів розміщення коней у останніх двох стовпчиках, бо в кожній з 8 клітинок кінь може або бути або не бути. Зобразимо два останні стовпчики дошки, позначивши однаковими літерами поля літерами латиниці A, B, C, D.
A    B
C    D
B    A
D    C
Для коней, розташованих на останніх стовпчиках дошки, бити один одного можуть лише пари коней, що знаходяться у клітинках, позначених у таблиці ліворуч однією літерою. При допустимих розташуваннях для кожної з цих пар маємо 3 варіанти: або немає коней на обох клітинках, або кінь є на першій (згори), або кінь є на другій. Тому загальна кількість позицій — допустимих розташувань коней на двох останніх стовпчиках дошки — дорівнює  3^4 = 81. Для кожного такої позиції визначимо, які позиції можна отримати при коректному долученні ще одного стовпчика. Тоді для підрахунку кількості розташувань на дошці 4×N для певної позиції k додаємо кількості розташувань на дошці 4×(N – 1) для тих позицій, з яких можна перейти у k долученням стовпчика і знаходимо остачу від ділення цієї суми на P. Кількість операцій у такому алгоритмі буде пропорційна 3^8∙N, що має прийнятний час при N ≤ 10000. Таке розв’язання набирає 70% балів.
Рівень 3. Позначимо через А матрицю розміром 81×81, у якій елемент у рядку k і стовпчику j дорівнює 1, якщо з позиції j можна перейти до позиції k, та дорівнює 0, якщо такий перехід неможливий.
Позначимо через Bn матрицю розміром 81×1 (вектор-стовпчик, що має 81 координату), де значення у комірці (k ; 1) дорівнює кількості розміщень у таблиці 4×N з кінцевою позицією k. Усі координати B2 дорівнюють 1.
Маємо:  А∙Bn = Bn + 1  і    A^(n – 2)∙B2 = Bn  при довільному натуральному n.
Кількість допустимих розташувань — це сума всіх елементів BN .
Найскладнішу частину алгоритму — підрахунок A^N – 2 — можна здій¬сни-ти за час, що пропорційний 81^3∙ logN. Для цього спочатку обчислимо матриці A, A^2, A^4, ... , A^(2s), для всіх S, при яких 2S не перевищує N – 2. Кожну з цих матриц можна вираховувати як квадрат поперед¬ньої, отже кількість операцій для вираховування кожної з них пропорційна 81^3. Далі множимо між собою ті степені матриці А, сума степенів яких дорівнює N – 2. Ці степені відповідають відмінним від нуля розрядам двійкового розкладу N – 2. Таке розв’язання набирає 100% балів.

Автор задачи: Сергей Могильный.

Відредаговано n1ce (2010-01-30 20:37:43)

Поза форумом

 

#12 2010-01-31 17:26:57

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

Вот задача Border кому интересно.
60 из 60 после исправления ошибки.

Код:

#include <iostream>
#include <math.h>
using namespace std;
#define PI 3.14159265359
//Структура для хранения окружностей
struct myStruct
{
    int x;
    int y;
    int r;
};
//Структура для хранения окружностей которые входяят выпуклую оболочку
struct myStack
{
    myStruct* p;
    myStack* pNext;
};


//Функция которая получает указатели на две оружности и вычисляет угол наклона левой касательной в радианах
//также через указатель rk передается длина касательной 
long double myAngle(myStruct* m1,myStruct* m2,long double *rk)
{
    long long rr,x21,y21,r21;
    long double x,y,rrk;
    if(m1==m2) return 0;
    x21=m2->x-m1->x;
    y21=m2->y-m1->y;
    r21=m1->r-m2->r;
    rr=x21*x21+y21*y21;
    rrk=sqrt((long double)(rr-r21*r21));
    x=(long double)(x21*rrk+y21*r21);
    y=(long double)(x21*r21-y21*rrk);
    *rk=rrk;
    return atan2(x,y)+PI;
}

//Добавление в очередь
myStack* AddStack(myStruct *pp, myStack *pst)
{
    myStack* p;
    p=new myStack;
    p->p=pp;
    p->pNext=NULL;
    if(pst!=NULL) pst->pNext=p; 
    return p;
}

//Удаление очереди
void DelStack(myStack *pp)
{
    myStack *p, *tp;
    p=pp;
    while(p!=NULL)
    {
        tp=p;
        p=p->pNext;
        delete tp;
    }
}

int main(void)
{
    myStruct *m;
    myStack *pst,*bst;
    int i,n,x,y,r;
    myStruct *pLD;
    long double rez;
    cin>>n;
    m=new myStruct[n];
    pLD=m;
    //чтение массива окружностей и вычисление левой нижней
    for(i=0;i<n;i++) 
    {
        cin>>x>>y>>r;
        m[i].x=x;
        m[i].y=y;
        m[i].r=r;
        if(x-r<pLD->x-pLD->r || (x-r==pLD->x-pLD->r && y<pLD->y))    pLD=&m[i];
    }
    //Добавление вычесленной окружности в очередь
    bst=pst=AddStack(pLD,NULL);
    long double dMax,dpMax,td,tdr,dr;
    myStruct *pMax;
    int f=1;
    dpMax=2*PI;
    rez=0;
    //сама процедура поиска выпуклой оболочки
    while(f)
    {
        dMax=0.0;
        pMax=pst->p;
        f=0;
        for(i=0;i<n;i++)
        {
            td=myAngle(pst->p,&m[i],&tdr); // вычисление угла касательной
            if(td<dpMax)// если угол меньше вычесленного для предыдущей окружности выпуклой оболочки
            {
                if(td>dMax)// если угол больше максимального
                {
                    f=1;
                    dMax=td;
                    pMax=&m[i];
                    dr=tdr;
                }
                else 
                {    
                    // если углы равны то проверяем данная окружнность дальше предыдущей найденой
                    if(td==dMax && (abs(pst->p->x-m[i].x)+abs(pst->p->y-m[i].y)-m[i].r)>(abs(pst->p->x-pMax->x)+abs(pst->p->y-pMax->y)-pMax->r))
                    {
                        f=1;
                        dMax=td;
                        pMax=&m[i];
                        dr=tdr;
                    }
                }
            }
        }
        if(f) // если удалось найти новую окружность
        {
            rez=rez+dr+(dpMax-dMax)*(pst->p->r+1);    // добавляем длину новой касательной и длину дуги для предыдущей окружности
                                                        // кстати тут и была моя ошибка вместо радиуса предыдущей подставлял радиус текущей
                                                        // за что набрал только 10 балов :( т.е. в тех тестах что прошли окружности выпуклой оболочки имели одинаковый радиус :)
            pst=AddStack(pMax,pst); // добавляем в очередь
            dpMax=dMax;
        }
    }
    rez=rez+dpMax*(pst->p->r+1); // вычисляем дугу последней окружности
    pst=bst;

    //*** Кому интересно можно убрать коментарии ниже и посмотреть окружности которые вошли в выпуклую оболочку
    //while(pst)
    //{
    //    cout<<pst->p->x<<','<<pst->p->y<<','<<pst->p->r<<endl;
    //    pst=pst->pNext; 
    //}

    // Ну собственно и все...
    cout.setf(ios::scientific,ios::floatfield);
    cout.precision(13);
    cout<<rez<<endl;
    DelStack(bst);
    delete[] m;
    return 0;
}

Відредаговано pilya (2010-01-31 17:29:51)

Поза форумом

 

#13 2010-01-31 20:26:19

Vinnie
Новий користувач
Зареєстрований: 2010-01-07
Повідомлень: 9

Re: Как делать задачи?

Спасибо.
Кстати, вот этот код 

pilya написав:

Код:

.....
                else 
                {    
                    // если углы равны то проверяем данная окружнность дальше предыдущей найденой
                    if(td==dMax && (abs(pst->p->x-m[i].x)+abs(pst->p->y-m[i].y)-m[i].r)>(abs(pst->p->x-pMax->x)+abs(pst->p->y-pMax->y)-pMax->r))
                    {
                        f=1;
                        dMax=td;
                        pMax=&m[i];
                        dr=tdr;
                    }
                }
.....

совсем не нужен, т.к. вряд ли он будет выполняться из-за td==dMax,
в чем не трудно убедиться запустив проверку без него.

И еще. Насколько я понял, программа работает за O(N^2)? sad

Відредаговано Vinnie (2010-01-31 20:29:57)

Поза форумом

 

#14 2010-01-31 20:47:40

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

Просто в тестах не предусмотрено нахождение нескольких окружностей к которым можно провести общую касательную.
А скорость совершенно верно N^2.
Я пытался применить к задаче другие методы поиска выпуклой оболочки, но этот мне показался самым оптимальным. По крайней мере в этом примере надо искать только длину касательной и угол наклона, а при реализации других других алгоритмов пришлось бы выполнять дополнительные математические вычисление, например для определения как одна окружность расположена относительно двух других, что привело бы к суммарному времени не меньше данного алгоритма.

Пусть меня поправит тот кто решил эту задачу другим способом.

Поза форумом

 

#15 2010-01-31 21:35:07

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Как делать задачи?

У меня есть одна английская статья, в которой описано, как решить ее за O(NlogN), но там довольно сложный алгоритм, в котором помимо кучи вычислительной геометрии требуется ручная реализация сбалансированного двоичного дерева. Если кому интересно, могу выложить.

Поза форумом

 

#16 2010-02-01 06:12:11

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

kadr написав:

У меня есть одна английская статья, в которой описано, как решить ее за O(NlogN), но там довольно сложный алгоритм, в котором помимо кучи вычислительной геометрии требуется ручная реализация сбалансированного двоичного дерева. Если кому интересно, могу выложить.

Очень даже интересно.

Поза форумом

 

#17 2010-02-01 08:45:16

Vinnie
Новий користувач
Зареєстрований: 2010-01-07
Повідомлень: 9

Re: Как делать задачи?

pilya написав:

Просто в тестах не предусмотрено нахождение нескольких окружностей к которым можно провести общую касательную.

По-моему Вам повезло smile, иначе ваша программа могла бы сработать  неправильно из-за сравнения td==dMax.
Смотреть например Про сравнение double

pilya написав:

А скорость совершенно верно N^2.
Я пытался применить к задаче другие методы поиска выпуклой оболочки, но этот мне показался самым оптимальным. По крайней мере в этом примере надо искать только длину касательной и угол наклона, а при реализации других других алгоритмов пришлось бы выполнять дополнительные математические вычисление, например для определения как одна окружность расположена относительно двух других, что привело бы к суммарному времени не меньше данного алгоритма.

Для определения относительного расположения окружностей Вы используете вычисление с помощью atan2 двух углов (N^2 раз). Мне кажется дешевле использовать псевдоскалярное произведение (см. Порублев, Ставровский. Алгоритмы и программы. Решение олимпиадных задач. Глава 6.).
Вашу программу можно улучшить, хотя бы исключая из дальнейшего рассмотрения уже найденные точки.

pilya написав:

Пусть меня поправит тот кто решил эту задачу другим способом.

Моя программа не набирает 60 баллов, поэтому поправлять не буду smile

Відредаговано Vinnie (2010-02-01 08:51:23)

Поза форумом

 

#18 2010-02-01 09:04:48

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

помоему вы не прониклись задачей smile одна окружность может участвовать в выпуклой оболочке максимум до 4 раз поэтому исключать окружности из рассмотрения нельзя.

Поза форумом

 

#19 2010-02-01 09:36:54

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Как делать задачи?

pilya написав:

помоему вы не прониклись задачей smile одна окружность может участвовать в выпуклой оболочке максимум до 4 раз поэтому исключать окружности из рассмотрения нельзя.

Почему только до 4? Представьте себе одну большую окружность, а вокруг нее равномерно распределены 5 маленьких, причем они лежат очень близко к границе большой. Тогда большая окружность даст 5 дуг в выпуклую оболочку. Если увеличить количество маленьких, то будет еще больше.
P.S.: Вот ссылка на ту статью, о которой я говорил выше.

Поза форумом

 

#20 2010-02-01 11:19:51

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

согласен с 4-мя погорячился smile
Спасибо за статью.

Поза форумом

 

#21 2010-02-01 19:34:30

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

Vinnie написав:

По-моему Вам повезло smile, иначе ваша программа могла бы сработать  неправильно из-за сравнения td==dMax.
Смотреть например Про сравнение double

Вопервых мне не повезло потому что я сдела другую ошибку, которую указал в коментариях sad
А во вторых не зыбывайте что коодинаты окружностей целые числа и поэтому функция вполне может вернуть два абсолютно одинаковых угла для этого и делается сравнение.

Vinnie написав:

Для определения относительного расположения окружностей Вы используете вычисление с помощью atan2 двух углов (N^2 раз). Мне кажется дешевле использовать псевдоскалярное произведение (см. Порублев, Ставровский. Алгоритмы и программы. Решение олимпиадных задач. Глава 6.).

Во первых atan2 используется не для нахождения взаимного расположения окружностей, а для определения угла касательной в радианах (хотя это вы могли прочитать и в коментариях). А псевдоскалярное произведение для определения взаимного расположения трех точек а не окружностей разного диаметра.

Vinnie написав:

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

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

P.S.Ваша ошибка слово точки, а задача про геометрическое место точек, находящихся на равном растоянии от точки. wink

Відредаговано pilya (2010-02-01 19:35:31)

Поза форумом

 

#22 2010-02-02 11:11:46

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Как делать задачи?

pilya написав:

Просто в тестах не предусмотрено нахождение нескольких окружностей к которым можно провести общую касательную.

В задачі взагалі вимагається не "нахождение окружностей", а знаходження мінімально можливої довжини огорожі. Якщо мова йде про те, що в тестах взагалі нема випадку кількох (строго більше двох) кіл зі спільною дотичною -- взагалі-то такі тести є. Але, можливо, й варто було продумати їх якось детальніше.

Проблема ж створюється не просто фактом наявності кількох кіл зі спільною дотичною, а тим, що вони водночас і мають спільну дотичну, і розглядаються в "незручному" порядку. А який порядок для якої програми буде "незручним" -- продумати наперед важко.

Відредаговано Ilya Porublyov (2010-02-02 12:23:32)

Поза форумом

 

#23 2010-02-02 13:50:01

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Как делать задачи?

Полностью с Вами согласен для этого и делалась проверка на окружность самую удаленную из всех что имеют общую касательную

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt