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

@maxx-96 · Регистрация: 28.10.2012

Студворк — интернет-сервис помощи студентам

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).Вручную вводятся количество вершин(n) и координаты каждой вершины x1,y1,... xn,yn.
3<=N<=1000; xi и yi -целые числа,по модулю не превосходящие 1000000.Выводится только число искомых точек. Программа должна быть написана в pascal abc.
Заранее спасибо!

.

@Puporev · 29.10.2012, 08:51

Если не ошибаюсь, нужно построить выпуклую оболочку и затем посчитать число точек внутри нее, или точки, которые не вошли в выпуклую оболочку. Хотя и не очень понятно, что значит внутри многоугольника.

@maxx-96 · 29.10.2012, 09:19 **[ТС]**

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

@Puporev · 29.10.2012, 09:48

Сообщение от maxx-96

ограниченной сторонами многоугольника.

Но они тоже являются вершинами многоугольника.

Добавлено через 5 минут
Вот посмотри задачу в графическом режиме на построение выпуклой оболочки. Если мысль верная, то тебе просто из общего количества вершин вычесть те, что входят в выпуклую оболочку.
Вся программа это что бы посмотреть, а тебе нужна только первая половина.

Pascal

{ Построение выпуклой оболочки множества }
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.

Добавлено через 20 минут
Пардон, я программу на Турбо Паскале скинул, забыл что раздел АВС. У тебя ТП не рулит?

@maxx-96 · 29.10.2012, 22:21 **[ТС]**

Нет!!

@Puporev · 30.10.2012, 09:07

Вот на АВС.

Pascal

{ Построение выпуклой оболочки множества }
uses crt,graphABC;
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;
for i:=1 to n do
used[i]:=false;
//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;
hidecursor;
clearwindow;
setwindowsize(600,600);
x0:=windowwidth div 2;
y0:=windowheight div 2;
ms:=(y0-30)/10;
line(x0-y0+10,y0,x0+y0-10,y0);
textout(x0+y0,y0-15,'X');
line(x0,10,x0,windowheight-10);
textout(x0+5,10,'Y');
textout(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);
  {подпись оси У}
  textout(x0-35,y0-round(i*ms),s);{соответственно засечкам}
  textout(x0-35,y0+round(i*ms),'-'+s);
  {подпись оси Х}
  textout(x0+round(i*ms),y0+10,s);
  textout(x0-round(i*ms),y0+10,'-'+s);
 end;
setpencolor(clBlue);
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));
setpencolor(clRed);
for i:=1 to n do
 begin
  circle(x0+round(p[i].x*ms),y0-round(p[i].y*ms),2);
  str(i,s);
  textout(x0+round(p[i].x*ms)+5,y0-round(p[i].y*ms),s);
 end;
end.

@maxx-96 0 / 0 / 0 Регистрация: 28.10.2012 Сообщений: 11
		1
	Подсчитать количество точек с целочисленными координатами, лежащих внутри многоугольника 29.10.2012, 00:06. Показов 7779. Ответов 5 Метки нет (Все метки) Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).Вручную вводятся количество вершин(n) и координаты каждой вершины x1,y1,... xn,yn. 3<=N<=1000; xi и yi -целые числа,по модулю не превосходящие 1000000.Выводится только число искомых точек. Программа должна быть написана в pascal abc. Заранее спасибо! . 0

@Puporev Почетный модератор 64291 / 47589 / 32740 Регистрация: 18.05.2008 Сообщений: 115,181
	29.10.2012, 08:51	2
	Если не ошибаюсь, нужно построить выпуклую оболочку и затем посчитать число точек внутри нее, или точки, которые не вошли в выпуклую оболочку. Хотя и не очень понятно, что значит внутри многоугольника. 0

@maxx-96 0 / 0 / 0 Регистрация: 28.10.2012 Сообщений: 11
	29.10.2012, 09:19 [ТС]	3
	Имеются в виду все точки, которые имеют целочисленные координаты и при этом лежат внутри части плоскости, ограниченной сторонами многоугольника. 0

@maxx-96 0 / 0 / 0 Регистрация: 28.10.2012 Сообщений: 11
	29.10.2012, 22:21 [ТС]	5
	Нет!! 0

Опции темы