Четырёхугольник ABCD задан координатами своих вершин на плоскости: A([latex]x_{a}[/latex],[latex]y_{a}[/latex]), B([latex]x_{b}[/latex],[latex]y_{b}[/latex]), C([latex]x_{c}[/latex],[latex]y_{c}[/latex]), D([latex]x_{d}[/latex],[latex]y_{d}[/latex]). Проверить, является ли он выпуклым.
Тесты:
| Точки | Координаты (x,y) | Вердикт |
| A,B,C,D | (1,1),(3,3),(5,2),(2,0) | Выпуклый |
| A,B,C,D | (-2,1),(2,2),(3,-1),(3,-1) | Выпуклый |
| A,B,C,D | (1,0),(1,3),(2,1),(5,0) | Не выпуклый |
| A,B,C,D | (-1,3),(0,0),(4,2),(-1,-3) | Не выпуклый |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <math.h> using namespace std; int f (int x, int x0, int x1, int y, int y0, int y1) { return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0); } int main() { double xa, ya, xb, yb, xc, yc, xd, yd; cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd; int l,m; l = f(xc,xb,xa,yc,yb,ya); m = f(xd,xb,xa,yd,yb,ya); if (l * m < 0) { printf("не выпуклый"); return 0; } int q,w; q = f(xa,xc,xb,ya,yc,yb); w = f(xd,xc,xb,yd,yc,yb); if (q * w < 0) { printf("не выпуклый"); return 0; } int p,r; p = f(xa,xd,xc,ya,yd,yc); r = f(xb,xd,xc,yb,yd,yc); if (p * r < 0) { printf("не выпуклый"); return 0; } int j,k; j = f(xb,xa,xd,yb,ya,yd); k = f(xc,xa,xd,yc,ya,yd); if (j * k < 0) { printf("не выпуклый"); return 0; } printf ("Выпуклый"); return 0; } |
Ссылка на код http://ideone.com/dsWBJc
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { static double f (double x, double x0, double x1, double y, double y0, double y1){ return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0); } public static void main (String[] args) throws java.lang.Exception { double xa, ya, xb, yb, xc, yc, xd, yd; Scanner in = new Scanner(System.in); xa = in.nextDouble(); ya = in.nextDouble(); xb = in.nextDouble(); yb = in.nextDouble(); xc = in.nextDouble(); yc = in.nextDouble(); xd = in.nextDouble(); yd = in.nextDouble(); double l,m; l = f(xc,xb,xa,yc,yb,ya); m = f(xd,xb,xa,yd,yb,ya); if (l * m < 0) { System.out.printf("не выпуклый"); return; } double q,w; q = f(xa,xc,xb,ya,yc,yb); w = f(xd,xc,xb,yd,yc,yb); if (q * w < 0) { System.out.printf("не выпуклый"); return; } double p,r; p = f(xa,xd,xc,ya,yd,yc); r = f(xb,xd,xc,yb,yd,yc); if (p * r < 0) { System.out.printf("не выпуклый"); return; } double j,k; j = f(xb,xa,xd,yb,ya,yd); k = f(xc,xa,xd,yc,ya,yd); if (j * k < 0) { System.out.printf("не выпуклый"); return; } System.out.printf(" Выпуклый "); } } |
Ссылка на код: ссылка
Ход решения:
Задаем уравнение прямой ([latex]\frac{x-x_{0}}{x_{1}-x_{0}}-\frac{y-y_{0}}{y_{1}-y_{0}}[/latex]). Преобразовываем его к виду без деления (чтобы не было проблем с делением на нуль) [latex](x-x_{0})*(y_{1}-y_{0})-(y-y_{0})*(x_{1}-x_{0})[/latex].
Для каждой стороны (AB,BC,CD,AD):
1. Строим уравнение прямой через эти две вершины.
2. Подставляем в формулу координаты остальных вершин.
3.Сравниваем значения вершин. Если их знаки разные — четырёхугольник не выпуклый.
Если для всех сторон данные условия выполнены — четырёхугольник является выпуклым.
Отлично! Зачтено.