1 / 1 / 0
Регистрация: 03.11.2011
Сообщений: 54
1

Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри многоугольника

01.11.2012, 19:59. Показов 2184. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
3. Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Прошу помочь с любой из задач. Буду признательна.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.11.2012, 19:59
Ответы с готовыми решениями:

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

Подсчитать количество точек с целочисленными координатами, лежащих внутри многоугольника
Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется...

Подсчитать количество точек с целочисленными координатами, лежащих внутри этого треугольника...
Целые точки Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или...

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

2
142 / 111 / 61
Регистрация: 01.08.2012
Сообщений: 297
02.11.2012, 12:14 2
Лучший ответ Сообщение было отмечено timupa80 как решение

Решение

Pascal
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
{ Построение выпуклой оболочки множества }
uses crt,graph;
type TPoint=record
            x,y: real;
            end;
     Tvyp=record
          x,y:real;
          k:integer;{номер точки}
          end;
 
const maxn=100;
 
{находится ли точка левее луча}
function IsLeft(p,p1,p2:TPoint):boolean;
begin
IsLeft:=(p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x)>0;
end;
 
var n,m,i,t1,t,newt:integer;
    x0,y0:integer;
    ms:real;
    s:string;
    p:array [1..maxn] of TPoint; {Точки множества}
    p1:array [1..maxn] of TVyp; {Точки выпуклой оболочки}
    used:array [1..maxn] of boolean;{Принадлежит-не принадлежит оболочке}
begin
clrscr;
randomize;
write('Количество точек n=');
readln(n);
writeln('Множество точек:');
for i:=1 to n do
 begin
  p[i].x:=-10+20*random;
  p[i].y:=-10+20*random;
  write('P[',i:2,'](',p[i].x:5:2,';',p[i].y:5:2,')  ');
  if i mod 4=0 then writeln;
 end;
t1:=1;{первая точка}
for i:=1 to n do
 begin
  if (p[i].y<p[t1].y) then t1:=i else
  if (p[i].y=p[t1].y) and (p[i].x<p[t1].x) then t1:=i;
 end;
FillChar(used,SizeOf(used),false);
writeln;
writeln;
writeln('Выпуклая оболочка идет через вершины: ');
t:=t1;
m:=0;
repeat
m:=m+1;
p1[m].x:=p[t].x;p1[m].y:=p[t].y;p1[m].k:=t;
used[t]:=true;
newt:=0;
{ Поиск следующей вершины }
for i:=1 to n do
if i<>t then
if (newt=0) or (IsLeft(p[t], p[i], p[newt]))then newt:=i;
t:=newt;
until t=t1;
for i:=1 to m do
write('P[',p1[i].k:2,'](',p1[i].x:5:2,';',p1[i].y:5:2,')  ');
if i mod 4=0 then writeln;
m:=m+1;
p1[m].x:=p1[1].x;p1[m].y:=p1[1].y;{замкнем оболочку}
writeln;
writeln;
write('Нажмите Enter для проверки результата графически');
readln;
initgraph(x0,y0,'');
x0:=getmaxX div 2;
y0:=getmaxY div 2;
ms:=(y0-10)/10;
line(x0-y0+10,y0,x0+y0-10,y0);
outtextXY(x0+y0,y0-15,'X');
line(x0,10,x0,getmaxY-10);
outtextXY(x0+5,10,'Y');
outtextXY(x0+5,y0+15,'0');
for i:=1 to 10 do
 begin
  line(x0-3,y0-round(i*ms),x0+3,y0-round(i*ms));{засечки на оси У}
  line(x0-3,y0+round(i*ms),x0+3,y0+round(i*ms));
  line(x0+round(i*ms),y0-3,x0+round(i*ms),Y0+3); {засечки на оси Х}
  line(x0-round(i*ms),y0-3,x0-round(i*ms),Y0+3);
  str(i,s);
  {подпись оси У}
  outtextXY(x0-35,y0-round(i*ms),s);{соответственно засечкам}
  outtextXY(x0-35,y0+round(i*ms),'-'+s);
  {подпись оси Х}
  outtextXY(x0+round(i*ms),y0+10,s);
  outtextXY(x0-round(i*ms),y0+10,'-'+s);
 end;
setcolor(14);
moveto(x0+round(p1[1].x*ms),y0-round(p1[1].y*ms));
for i:=1 to m do
lineto(x0+round(p1[i].x*ms),y0-round(p1[i].y*ms));
setcolor(12);
for i:=1 to n do
 begin
  circle(x0+round(p[i].x*ms),y0-round(p[i].y*ms),1);
  str(i,s);
  outtextXY(x0+round(p[i].x*ms)+5,y0-round(p[i].y*ms),s);
 end;
readln
end.
Исходник
1
1 / 1 / 0
Регистрация: 03.11.2011
Сообщений: 54
07.11.2012, 14:40  [ТС] 3
Спасибо
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.11.2012, 14:40
Помогаю со студенческими работами здесь

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

Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R
Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R с...

Найти количество точек с целочисленными координатами лежащих внутри круга используя рекурсию
Найти количество точек с целочисленными координатами, лежащих внутри круга радиуса r Нужно...

Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R с центром в точке (х0, у0).
Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru