Пифагор только с одной известной стороной / Вычислительная геометрия

Question

Изображение проблемы

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

Описание задачи кодирования: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=861

Я создал класс Node с x-координатами и y-координатами и поместил их в очередь с приоритетами в первую очередь слева.

double totalLength = 0;
Node peak = priorityQueue.poll();
Node col = null;
while (!priorityQueue.isEmpty()) {
    Node nextCoordinates = priorityQueue.poll();
    if (peak.yCo > nextCoordinates.yCo) {
        col = nextCoordinates;
    } else {
        // DO SOME CALCULATIONS 
        peak = nextCoordinates;
    }
}
System.out.println(totalLength);

Я ищу вычисление, объясненное на рисунке вверху, и возможное лучшее решение проблемы кодирования во-вторых.Спасибо

Answer 1

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

Вот несколько псевдокодов:

Sort array of points, P, by x descending

sun = 0
high = 0
for i = 1 to P.length-1
  if P[i].y > P[high].y
    a = P[i].y - P[i-1].y
    b = P[i].x - P[i-1].x
    hdiff = P[i].y - P[high].y
    sun = sun + hdiff*sqrt(a*a+b*b)/a
    high = i
  end
end

Перевод на Java:

static double calculateSun(int[] peaks)
{
  Point[] pts = new Point[peaks.length/2];
  for(int j=0, i=0; i<peaks.length; j++) 
    pts[j] = new Point(peaks[i++], peaks[i++]);

  // Sort by X descending
  Arrays.sort(pts, (p1, p2) -> {return p2.x - p1.x;});

  double sun = 0;    
  for(int h=0, i=1; i<pts.length; i++)
  {
    if(pts[i].y > pts[h].y)
    {
      int a = pts[i].y - pts[i-1].y;
      int b = pts[i].x - pts[i-1].x;
      int hdiff = pts[i].y - pts[h].y;
      sun += hdiff*Math.sqrt(a*a + b*b)/a;        
      h = i;
    }
  }
  return sun;
}

Тест:

public static void main(String[] args)
{
  int[][] tests = {
      { 1100, 1200, 0, 500, 1400, 100, 600, 600, 2800, 0, 
        400,  1100, 1700, 600, 1500, 800, 2100, 300, 
        1800, 700, 2400, 500, },
      {
        0, 1000, 1000, 0, 
      }};

  for (int[] test : tests)
    System.out.printf("%.2f\n", calculateSun(test));
}

Вывод:

1446.34
1414.21

Что соответствует ожидаемому результату.