Текущ брой на Списание ИнфоМан
 


Зимни Математически Състезания 2005, Задача A1. РАЗСТОЯНИЯ

Условието на задачата може да прочетете тук.

Решение

Задачата може да се реши като на всяка точка се съпоставят въображаеми координати. Така след това ще е лесна задача да се намерят разстоянията от дадената точка до всички други. Как можем да направим това? Фиксираме си дадените две точки (които знаем, че са от изпъкналата обвивка). Например можем да им съпоставим координатите (0,0) и (0,d), където d е разстоянието между тях. Как ще намерим останалите точки. Ако имаме две фиксирани точки и знаем, че има нефиксирана тока, която е свързана с тях (т.е. знаем разстоянието до нея от двете фиксирани), това се свежда до позната задача от математиката: като знаем трите страни на тригълник и едната страна вече е построена да построим и другите две. Задачата се решава като начертаем окръжности около двете фиксирани точки с радиуси съответно равни на разстоянията им до нефиксираната точка. Където двете окръжности се пресичат, там е и третата точка. За съжаление има две такива точки, но сега ще покажа как да избираме само едната от тях.

Насочено лице на триъгълник се нарича векторното произведение на два вектора, които започват от един връх на триъгълника. Насочено е, защото благодарение на тази функция ние можем да знаем дали ъгълът ABC на триъгълника ABC завива по часовника или обратно. Ето как се пресмята насоченото лице на триъгълник: Ако координатите на триъгълника са A=(x1,y1),B=(x2,y2),C=(x3,y3), тогава резултатът е следният:

(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1).

Ако е положителен, тогава ъгълът ABC завива обратно на часовниковата стрелка. Ако е нула ъгълът е 180 градуса.

Като си фиксираме двете начални точки (p1,p2) ние искаме всички останали точки да са такива, че ъгълът p1p2pXда е винаги обратен на часовника. Това е възможно понеже реброто p1p2 лежи на изпъкналата обвивка. Ето как можем да генерираме всички точки така, че да е спазено това:

Използваме структура, която ни позволява да вадим и слагаме елементи (опашка или стек, но може би опашката е по подходяща - постига се по-голяма точност при изчисленията). Отначало слагаме реброто (p1,p2) в нея, което означава, че търсим такива точки px, които са свързани с двете в опашката така че ъгълът p1->p2->px да е обратен на часовника , и на всяка стъпка правим следното: Вадим ребро (a,b) от опашката и гледаме с кои други точки е свързано. Ако има някоя неопределена точка px с която е свързано (то тя задължително ще е такава, че насоченото лице a->b->px ще е обратно на часовника - това лесно се вижда като се разгледат свойствата на триангулацията), то можем да изчислим координатите й. Като сме ги изчислили слагаме в структурата две нови ребра: (a,px), (px,b) и повтаряме същата процедура. Когато намерим някаква точка, която е свързана с двата края на ребротои намерим координатите и, трябва да изтрием ребрата, които слагаме в опашката, за да не ни пречат после. Те повече няма да ни трябват, тъй като свързват вече фиксирани точки.

Сега ще обясня методите, по които се изчисляват пресечните точки на две окръжности.


Чертеж 1. Намиране на пресечна точка на две окръжности

1) Всяка окръжност си има уравнение с две неизвестни, а след като имаме и две уравнения можем без проблеми да решим системата. За улеснение можем да ги транслираме така че едната окръжност да е центрирана в (0,0) и да ротираме спрямо центъра и другата. После като сметнем пресечната точка, ще направим обратните преобразувания.

2) Виж чертежа. Метод с питагорови теореми. Знаем AB, ra, rb. Намираме CD чрез формулата за лице на триъгълник (може хероновата да използваме). Намираме от триъгълник ACD, AD. Тогава намираме и точка D, след това с ротация можем да намерим точка C. Ние търсим точка C, защото тя е такава, че ъгълът ABC е по обратната на часовника посока. Само че има три частни случая тук, които трябва да се разгледат поотделно.

3) Виж черетежа. Метод с косинусови теореми (който използвам в мойто решение). Намираме ъглите на ABC с косинусови теореми (т.е. намираме косинусите им). Тогава ротираме отсечката AB алфа градуса обратно на часовника и после новополучената отсечка я удължаваме (или скъсяваме) да стане дълга колкото AC. Долу съм сложил формулите за ротация и променяне на дължината на отсечка.

4) Метод с полярни ъгли. Вижте решението на журито.

От всички методи може би 4-ти дава най - коректни резултати, като моето решение едва работи, когато входа е зададен с 16 знака след запетаята, а не с 8.

Преди да извършим следните две операции транслираме отсечката така че началото й да е в (0,0), после я връщаме обратно.

Ето и формула за ротация: приемаме, че ротираме точка около (0,0) понеже сме транслирали едната точка на отсечката.

x1=cosA*x-sinA*y

y1=sinA*x+cosA*y

където А е ъгълът по посока обратна на часовника, с който завъртаме точката (x,y) a (x1,y1) е новата точка.

Ето и за промяна на размера:искаме новата точка да е на разстояние K от (0,0) в същата посока както и преди.

x1=x/sqrt(x*x+y*y)*k

y1=y/sqrt(x*x+y*y)*k

Примерна реализация:

#include <math.h>
#include <stdio.h>

#define mx 1024
#define in stdin;

FILE*fn;
typedef struct {double x,y;} point;
typedef struct {int a,b;} edge;
point p[mx];

//////////////
edge q[mx*8];
int qin,qou;
int atq(edge a){q[qin++]=a;return 0;}
edge gfq(void){return q[qou++];}

//////////////
int ok[mx];
int ss[mx][mx];
double dist[mx][mx];
int q1,q2,q3,c1,c2,c3;

///////////////////////////////////////
double dist2(point a,point b)
  {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
point resize(point a,point b,double len)
  {double c1,c2,c3;
  point c;
  c.x=b.x-a.x;
  c.y=b.y-a.y;
  c1=dist2(a,b);
  c.x=c.x/c1*len;
  c.y=c.y/c1*len;
  c.x+=a.x;
  c.y+=a.y;
  return c;}
point get2(point a,point b,double ra,double rb)
  {double c1,c2,cosa,sina;
  point p1,p2,p3;
  c1=dist2(a,b);
  cosa=(ra*ra+c1*c1-rb*rb);
  cosa/=(2.0*ra*c1);
  sina=sqrt(1.0-cosa*cosa);
  p1.x=b.x-a.x;
  p1.y=b.y-a.y;

  p2.x=p1.x*cosa-p1.y*sina;
  p2.y=p1.x*sina+p1.y*cosa;

  p2.x+=a.x;
  p2.y+=a.y;
  p3=resize(a,p2,ra);

  return p3;}
double cosa(point a,point b,double ra,double rb)
  {double aa,bb,cc,c1;
  aa=rb;
  bb=ra;
  cc=dist2(a,b);
  c1=(cc*cc+bb*bb-aa*aa)/(2.0*cc*bb);
  return c1;}
  
///////////////////////////////
edge e1,e2;
point p1,p2;
int start,c;
double w1,w2,w3,w4;
int main()
  {fn=in;
  fscanf(fn,"%d %d %d",&c,&e1.a,&e1.b);
  e1.a--;
  e1.b--;
  start=e1.a;
  while(1)
    {if(fscanf(fn,"%d %d %lf",&c1,&c2,&w1)!=3)break;
    c1--;c2--;
    ss[c1][c2]=ss[c2][c1]=1;
    dist[c1][c2]=dist[c2][c1]=w1;}
  fclose(fn);
  p1.x=0.0;
  p1.y=0.0;
  p[e1.a]=p1;
  p1.x=dist[e1.a][e1.b];
  p1.y=0.0;
  p[e1.b]=p1;
  ok[e1.a]=ok[e1.b]=1;
  atq(e1);ss[e1.a][e1.b]=0;

  while(qin!=qou)
    {e1=gfq();
    w3=-19.0;
    c1=-1;
    for(q1=0;q1<c;q1++)if(ss[e1.a][q1]&&ss[q1][e1.b])
      {
      w2=cosa(p[e1.a],p[e1.b],dist[e1.a][q1],dist[e1.b][q1]);
      if(w2>w3)
        {w3=w2;
        c1=q1;}}
    if(c1==-1)continue;
    p1=get2(p[e1.a],p[e1.b],dist[e1.a][c1],dist[e1.b][c1]);

    if(!ok[c1])
      {ok[c1]=1;
      p[c1]=p1;}
    e2.a=e1.a;
    e2.b=c1;
    atq(e2);ss[e2.a][e2.b]=0;
    e2.a=c1;
    e2.b=e1.b;
    atq(e2);ss[e2.a][e2.b]=0;
    }

  for(q1=0;q1<c;q1++)printf("%.2lf\n",dist2(p[start],p[q1]));
  return 0;}

Автор: Светослав Колев


обратно към брой 27