E076. Знаковая площадь треугольника и предикат "По часовой стрелке"

e-maxx algorithm original: C/C++ #algorithm #emaxx #graph

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

Static

Источник: e-maxx.ru/algo, страница PDF 226.

정의

Пусть given три точки

,

. Найдём значение знаковой площади

треугольника

, т.е. площади этого треугольника, взятой со знаком плюс или минус в зависимости от типа поворота, образуемого точками

,

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

Вычисление

Воспользуемся понятием косого (псевдоскалярного) произведения векторов. Оно как раз равно удвоенной знаковой площади треугольника:

где угол

берётся ориентированным, т.е. это угол вращения между этими векторами против часовой стрелки. (Модуль косого произведения двух векторов равен модулю векторного произведения их.) Косое произведение вычисляется как величина определителя, составленного из координат точек: Раскрывая определитель, можно получить такую формулу: Можно сгруппировать третье слагаемое с первыми двумя, избавившись от одного умножения: Последнюю формулу удобно записывать и запоминать в матричном виде, как следующий определитель:

구현

Функция, вычисляющая удвоенную знаковую площадь треугольника:

int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) {

return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

} Функция, возвращающая обычную площадь треугольника: double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {

return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;

} Функция, проверяющая, образует ли указанная тройка точек поворот по часовой стрелке:

bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {

return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;

} Функция, проверяющая, образует ли указанная тройка точек поворот против часовой стрелки:

bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {

return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;

}

C# 해법

자동 초안, 제출 전 검토

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) {
            return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    }
    double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
            return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;
    }
    bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
            return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;
    }
    bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
            return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;
    }
}

C++ 해법

매칭됨/원본

int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) {
        return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}
double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
        return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;
}
bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
        return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;
}
bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
        return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;
}

Java 해법

자동 초안, 제출 전 검토

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) {
            return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    }
    double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
            return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;
    }
    boolean clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
            return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;
    }
    boolean counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
            return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;
    }
}

Материал разбит как 알고리즘ическая 문제: изучить постановку, понять асимптотику и реализовать 알고리즘 на выбранном языке.

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.