Kəsişən nərdivanlar#1506

Kəsişən nərdivanlar (Həll təhlili)

Üçbucaqlar $A O P$ və $A D C$ bənzərdir: $\frac{c}{b} = \frac{A P}{A C}$ \frac{c}{b} = \frac{AP}{AC}

Üçbucaqlar $C O P$ və $C B A$ bənzərdir: $\frac{c}{a} = \frac{C P}{C A}$ \frac{c}{a} = \frac{CP}{CA}

\frac{c}{b} + \frac{c}{a} = \frac{A P}{A C} + \frac{C P}{A C} = \frac{A C}{A C} = 1

\frac{c}{b} + \frac{c}{a} = \frac{AP}{AC} + \frac{CP}{AC} = \frac{AC}{AC} = 1

Buradan

c (\frac{1}{a} + \frac{1}{b}) = 1, c = \frac{1}{\frac{1}{a} + \frac{1}{b}} = \frac{ab}{a + b}

c \left( \frac{1}{a} + \frac{1}{b} \right) = 1, c = \frac{1}{\frac{1}{a} + \frac{1}{b}} = \frac{ab}{a + b}

Küçənin eni $d = A C$ d = AC ni binar axtarış metodu ilə tapacağıq.

Əvvəlcə $0 \leq d \leq min (x, y)$ 0 \le d \le min(x, y) olaraq qəbul edək. $d, x$ və $y$ qiymətlərini bilərək $a, b$ və $c$ yi hesablamaq olar. Sabit $x$ və $y$ ilə, $d$ artdıqca, $c$ azalır.

Alqoritmin realizasiyası

Hər test üçün giriş məlumatlarını oxuyuruq.

while(scanf("%lf %lf %lf",&x,&y,&c) == 3)
{

Dəyərləri təyin edirik: $l e f t = 0, r i g h t = min (x, y)$ left = 0, right = min(x,y). Dövrlə yerinə yetirmə prosesində həmişə $l e f t \leq d \leq r i g h t$ left \le d \le right bərabərsizliyi icra edilir.

  left = 0;
  if (x < y) right = x; else right = y;
  d = (left + right) / 2;
  do
  {

Dəyərləri $a, b, c$ a, b, c i hesablayırıq.

    a = sqrt(x*x - d*d); b = sqrt(y*y - d*d);
    c1 = 1/(1/a + 1/b);

Əgər hesablanmış $c 1$ dəyəri verilmiş $c$ dəyərindən kiçikdirsə, $d$ nn üst həddini azaltmaq lazımdır. Əks halda isə alt həddi artırmaq gərəkdir.

    if (c1 < c) right = (left + right) / 2;
           else left = (left + right) / 2;
    d = (left + right) / 2;

Hesablamalar məsələnin şəraitində tələb olunan dəqiqiliyə - dörd ondalıq yerə qədər icra edilir.

	 } while (fabs(c1 - c) > 0.00001);

Nəticəni çıxarırıq.

  printf("%.3lf\n",d);
}

Java implementasiyası

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    con.useLocale(new Locale("US"));
    while(con.hasNext())	  
    {
      double x = con.nextDouble();
      double y = con.nextDouble();
      double c = con.nextDouble();
      double Left = 0, Right, a, b, c1;
      if (x < y) Right = x; else Right = y;
      double d = (Left + Right) / 2;
      do
      {
        a = Math.sqrt(x*x - d*d); 
        b = Math.sqrt(y*y - d*d);
        c1 = 1/(1/a + 1/b);
        if (c1 < c) Right = (Left + Right) / 2;
               else Left = (Left + Right) / 2;
        d = (Left + Right) / 2;
      } while (Math.abs(c1 - c) > 0.00001);
      System.out.format(Locale.US,"%.3f\n",d);
    }
  }
}

C++