Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C] Решение задачи про многоугольник и точку.

Автор: 2FED 27.5.2008, 00:17

Типовая задача повышенной сложности:

На плоскости координатами своих упорядоченных вершин заданы произвольный многоугольник без самопересечения и точка а, находящаяся вне многоугольника. Определить число вершин, видимых из точки а.

Автор: maxim1000 27.5.2008, 11:46

по-простому можно так:
рассматриваем каждый отрезок из a в вершину, смотрим, не пересекается ли он с какой-нибудь стороной многоугольника
пересекается - точка скрыта, не пересекается - видна

сложность N^2
наверное, можно оптимизировать

Автор: 2FED 27.5.2008, 14:32

А как задать многоугольник без самопересечения?

Автор: maxim1000 27.5.2008, 15:27

ну например, как последовательность вершин

Автор: 2FED 27.5.2008, 18:21

вот пока часть моей программы:

Код


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define rnd (rand()%100-50)
void main()
{
 clrscr();
 int n,*x,*y,i;
 printf("Введите количество вершин : ");
 scanf("%d", &n);
 x=(int*)malloc(n*sizeof(int));
 y=(int*)malloc(n*sizeof(int));
 for(i=0;i<n;i++)
  {
   *x=rnd;
   *y=rnd;
   printf("%d %d\n", *x,*y);
  }
 getch();
}

В цикле я генерирурую вершины. А как сделать, чтобы многоугольник получался без самопересечения?

Автор: maxim1000 28.5.2008, 00:20

хм... это уже другая задача
есть очень простой способ (хотя не знаю, насколько быстрый)

1. генерируем произвольную последовательность точек
2. ищем самопересечения
3. если нашли - всё повторяем сначала
по идее, рано или поздно закончим

красотой и скоростью такой способ, по-моему, не блещет, зато куда уж проще smile

Автор: 2FED 28.5.2008, 01:56

А как найти эти самопересечения?

Автор: maxim1000 28.5.2008, 10:05

ну поперебирать все пары отрезков и проверить, не пересекаются ли они
(по определению пересечения отрезков стоит поискать тему - уже была)