Точка в Многоугольнике!

@greategi · Регистрация: 13.02.2012

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

Задача "Точка в многоугольнике".
Условие. Многоугольник (выпуклый) задан координатами своих вершин
(xi;yi), 1 i N в порядке обхода. Определить, лежит ли точка с координатами
(x0;y0) внутри или вне многоугольника.
Входные данные содержатся в файле input.txt: в первой строке - пара чисел
(x0;y0), в каждой (i+1)-й строке - координаты i-й точки (xi;yi).
Выходные данные нужно вывести в файл output.txt: единственная строка
этого файла должна содержать одно число - 1, если точка внутри многоугольника
(или на его стороне), 0 - в противном случае. (Необезательно делать с помошью файлов)
Пример

Input.txtt Output.txt Input.txt Output.txt
5 3
1 1
6 3
7 6
4 8
2 8
1 5
Ответ
1
7 3
1 1
6 3
7 6
4 8
2 8
1 5
Ответ
0

Вот что я сделал

C++
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
#include <iostream>
using namespace std;
struct Point{
int x;
int y;
 
};
void main()
{
Point O,line;
Point* mass = new Point[6] ;
 
O.x=5;
O.y=3;
mass[0].x=mass[0].y=1;
mass[1].x=6;
mass[1].y=3;
mass[2].x=7;
mass[2].y=6;
mass[3].x=4;
mass[3].y=8;
mass[4].x=2;
mass[4].y=8;
mass[5].x=1;
mass[5].y=5;
 
line.y=3;
line.x=0;
 
int k=0,b=0;
int g,a, TX,TY, count,U;
//
// Y(X) = k * X + b
//Y(X1) = Y1
//Y(X2) = Y2
k = 0;
b = O.y;
 
for(int i=0;i<6;i++)
{
 
 g = (mass[i+1].y-mass[i].y)/(mass[i+1].x-mass[i].x);
 a=(mass[i].y-g*mass[i].x);
 TX = (a - b) / (k - g);
 TY = k * TX + b;
 if(TY!=0&&TX!=0)
     count++;
 
 
 if(count%2==0)
     U=1;
 else 
     U=0;
 
 
 
}
 
cout<<U;
}

Но вот выдает (Необработанное исключение в "0x00411523" в "lab7.exe": 0xC0000094: Integer division by zero.) А потом желтая стрелка указывает на TX = (a - b) / (k - g); И еше пишет что неиницыалезированая переменная count.

Добавлено через 17 минут

C++
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
#include "stdafx.h"
#include <iostream>
using namespace std;
struct tochka
 {
  int xx;
  int yy;
 };
 
void main()
{
 tochka *t;int x,y,i;
 
 cout<<"Enter x & y:\n";
 cin>>x>>y;
 
 FILE *f1;
  
  f1=fopen("tochki.txt","r");
  
  while(!feof(f1))
   {
    fscanf(f1,"%s",&t[i].xx);
    fscanf(f1,"%s",&t[i].yy);
    i++;
   }
  fclose(f1); 
 
 int maxX,minX,maxY,minY;
 maxX=t[0].xx;minX=t[0].xx;maxY=t[0].yy;minY=t[0].yy;
 for(i=0;i<i;i++)
  {
   if(t[i].xx>maxX)
    {
     maxX=t[i].xx;
    }
   if(t[i].xx < minX)
    {
     minX=t[i].xx;
    }
  }
  for(i=0;i<i;i++)
   {
    if(t[i].yy>maxY)
    {
     maxY=t[i].yy;
    }
   if(t[i].yy < minY)
    {
     minY=t[i].yy;
    }
   }
   
 for(i=0;i<i;i++)
  {
   cout<<"\n"<<i+1<<" Tochka:"<<t[i].xx<<" "<<t[i].yy;
  }
  cout<<"\nMAXX = "<<maxX<<" MINX = "<<minX<<" MAXY = "<<maxY<<" MINY = "<<minY;  
    
  if((x<maxX)&&(x>minX)&&(y<maxY)&&(y>minY))
   {
    cout<<"\n\nTochka x,y lezut v mnogokytnikom";
   }
  else cout<<"\n\nTochka x,y lezut za mnogokytnikom";  
 
  system("pause");
}

Добавлено через 1 минуту
Вот робочая прога но она для треугольника помогите сделать для многоугольника! Пожалуста ! Буду благодарен.

C++
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
    #include "stdafx.h"
    #include <iostream>
    #include <math.h>
 
    using namespace std;
 
struct point
{
   int x;
   int y;
};
//площадь
int area(point a, point b, point c)
{
   return abs((a.x - c.x)*(b.y - c.y) + (b.x-c.x)*(c.y-a.y));
}
 
int main()
{
setlocale(LC_ALL, "rus");
   /////////////////////////////////////////////////////////////////////////////
   point a, b, c, d;
   cout << "Введите сначала координаты вершин треугольника, а затем "
        << "координаты точки:" << endl;
   cin >> a.x >> a.y;
   cin >> b.x >> b.y;
   cin >> c.x >> c.y;
   cin >> d.x >> d.y;
   /////////////////////////////////////////////////////////////////////////////
   //Если точка внутри, то суммарная площадь треугольников ABK, BCK, CAK равна площади ABC. Площадь треугольника считается как 1/2 abs (x1y2-x2y1 + x2y3-x3y2 + x3y1-x1y3).
   if (area(a, b, c))
   {
      if (area(a, b, c) == area(a, b, d) + area(a, d, c) + area(b, d, c))
            cout << "Точка находится внутри треугольника\n";
      else 
            cout << "Точка находится вне треугольника\n";
   }
   else
      cout << "Треугольник не существует\n";
   /////////////////////////////////////////////////////////////////////////////
   system("pause");
   return 0;
}

Добавлено через 22 минуты
Вот еше нашел в инете функцію помогите плз

C++
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
bool IsPointInside(Array<const Point2f> polygon, Point2f point)
{
    if (polygon.size <= 1)
        return false;
 
    int intersections_num = 0;
    int prev = polygon.size - 1;
    bool prev_under = polygon[prev].y < point.y;
 
    for (int i = 0; i < polygon.size; ++i)
    {
        bool cur_under = polygon[i].y < point.y;
 
        Point2f a = polygon[prev] - point;
        Point2f b = polygon[i]  - point;
 
        float t = (a.x*(b.y - a.y) - a.y*(b.x - a.x));
        if (cur_under && !prev_under)
        {
            if (t > 0)
                intersections_num += 1;
        }
        if (!cur_under && prev_under)
        {
            if (t < 0)
                intersections_num += 1;
        }
 
        prev = i;        
        prev_under = cur_under;        
    }
 
    return (intersections_num&1) != 0;
}

@UFO94 · 06.05.2012, 22:20

Опишите, пожалуйста, ваш математический алгоритм.
И попробуйте обьявить count в отдельной строке, и всегда(!!!) инициализируйте переменные перед использованием, т.е. либо

C++
1
int count=0;

Либо

C++
1
2
3
int count;
....
count=0;

@greategi · 10.05.2012, 11:04 **[ТС]**

пробовал

C++
1
int count=0;

всеравно проблека там в той строчке !Необработанное исключение в "0x00411523" в "lab7.exe": 0xC0000094: Integer division by zero.) А потом желтая стрелка указывает на TX = (a - b) / (k - g);

Ternsip · 13.05.2012, 19:55

C++
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
#include <iostream>
using namespace std;
struct Point{
int x;
int y;
 
};
void main()
{
Point O,line;
Point* mass = new Point[6] ;
 
O.x=5;
O.y=3;
mass[0].x=mass[0].y=1;
mass[1].x=6;
mass[1].y=3;
mass[2].x=7;
mass[2].y=6;
mass[3].x=4;
mass[3].y=8;
mass[4].x=2;
mass[4].y=8;
mass[5].x=1;
mass[5].y=5;
 
line.y=3;
line.x=0;
 
int k=0,b=0;
int g,a, TX,TY, count,U;
//
// Y(X) = k * X + b
//Y(X1) = Y1
//Y(X2) = Y2
k = 0;
b = O.y;
 
for(int i=0;i<6;i++)
{
 
 g = (mass[i+1].y-mass[i].y)/(mass[i+1].x-mass[i].x);
 a=(mass[i].y-g*mass[i].x);
 if (k!=g) TX = (a - b) / (k - g);else TX=99999; 
 if (k!=g) TY = k * TX + b;else TY=99999;
 if(TY!=0&&TX!=0)
     count++;
 
 
 if(count%2==0)
     U=1;
 else 
     U=0;
 
 
 
}
 
cout<<U;
}

Я избавился там от деления на 0

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .