Форум программистов, компьютерный форум CyberForum.ru

Точки в многоугольнике - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
19.03.2011, 14:18     Точки в многоугольнике #1
В общем не давно была олимпиада. и меня меня мучает решение одной задачи:


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

Входные данные

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

Выходные данные

В исходном потоке должно содержаться число - искомое количество точек.

Решать не прошу, хотя бы идею.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
20.03.2011, 16:15     Точки в многоугольнике #2
Некоторые идеи здесь: Как проверить принадлежит ли точка треугольнику?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 17:52     Точки в многоугольнике #3
IrineK, неа, здесь нужно применить теорему Пика

Добавлено через 22 секунды
Overmind024, сейчас выложу код...
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
20.03.2011, 17:58  [ТС]     Точки в многоугольнике #4
буду благодарен))
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 18:04     Точки в многоугольнике #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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 <iostream>
#include <vector>
////////////////////////////////////////////////////////////////////////////////
using namespace std;
////////////////////////////////////////////////////////////////////////////////
int gcd (int a, int b)
{
   while (b > 0)
   {
        int c = a%b;
        a = b;
        b = c;
    }
    return a;
}
////////////////////////////////////////////////////////////////////////////////
float sq (vector <pair <int, int> > v)
{
   float res = 0;
   for (int i = 0; i < v.size(); i++)
   {
      pair <int, int> one, two;
      one = i ? v[i-1] : v.back();
      two = v[i];
      res += (one.first - two.first)*(one.second + two.second);
   }
   return fabs(res)/2;
}
////////////////////////////////////////////////////////////////////////////////
int kt (vector <pair <int, int> > v)
{
   int res = 0;
   for (int i = 0; i < v.size(); i++)
   {
      pair <int, int> one, two;
      one = i ? v[i-1] : v.back();
      two = v[i];
      int dx, dy;
      dx = abs(one.first - two.first);
      dy = abs(one.second - two.second);
      res += gcd (dx, dy);
   }
   return res;
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
   locale::global(locale(""));
   cout << "Введите количество вершин: ";
   int n;
   cin >> n;
   
   vector <pair <int, int> > poligon;
   for (int i = 0; i < n; i++)
   {
      int x, y;
      cin >> x >> y;
      poligon.push_back(make_pair(x, y));
   }
   
   int M = kt(poligon);
   int S = (int)sq(poligon);
   int K = S - M/2 + 1;
   cout << "Количество точек с целочисельными координатами " 
        << "равно " << K << endl;
   return 0; 
}


Добавлено через 1 минуту
проверьте...

Добавлено через 4 минуты
+самое крутое решение
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
20.03.2011, 18:08  [ТС]     Точки в многоугольнике #6
Mayonez, спасибо буду разбираться!!
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 18:09     Точки в многоугольнике #7
Overmind024, если не секрет, что за олимпиада?
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
20.03.2011, 19:07  [ТС]     Точки в многоугольнике #8
Mayonez, не секрет. Всеукраинская олимпиада по программированию. Тренировка I.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 20:45     Точки в многоугольнике #9
delete
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
20.03.2011, 23:11  [ТС]     Точки в многоугольнике #10
Mayonez, пишет
Неправильный ответ Ошибка на тесте 7
я не много исправил так как вектор не хотел принимать. вот что получилось:
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
 
int abs(int a)
{
    return a>0?a:-a;
}
 
double dabs(double a)
{
    return a>0?a:-a;
}
 
struct point 
{
    int x;
    int y;
};
 
int nod (int a, int b)
{
    while (a && b)
    {
        if (a>b)
            a = a%b;
        else
            b = b%a;
    }
    return a+b;
}
 
double sq (point* v,int n)
{
    point one = v[n-1],
          two = v[0];
 
    double res = (one.x - two.x)*(one.y + two.y);
    for (int i = 1; i < n; i++)
    {
        one = v[i-1];
        two = v[i];
        res += (one.x - two.x)*(one.y + two.y);
    }
    return dabs(res)/2;
}
 
int kt (point* v,int n)
{
    point one = v[n-1],
          two = v[0];
    int dx = abs(one.x - two.x),
        dy = abs(one.y - two.y);
    int res = nod (dx, dy);
    for (int i = 1; i < n; i++)
    {
        one = v[i-1];
        two = v[i];
 
        dx = abs(one.x - two.x);
        dy = abs(one.y - two.y);
        res += nod (dx, dy);
    }
    return res;
}
 
int main()
{
 
    int n;
    scanf("%d",&n);
 
    point poligon[10000];
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d",&poligon[i].x,&poligon[i].y);
    }
 
    int M = kt(poligon,n);
    double S = sq(poligon,n);
    int K = S - M/2 + 1;
    printf("%d\n",K);
    return 0;
}
я не много не понимаю схему вычесления плошади, а именно:
C++
1
res += (one.x - two.x)*(one.y + two.y);
почему с начало минус а потом плюс??
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2011, 11:44     Точки в многоугольнике
Еще ссылки по теме:

C++ Посчитать количество углов в многоугольнике, образованном единицами в матрице
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки C++
Лежит ли точка в многоугольнике C++

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

Или воспользуйтесь поиском по форуму:
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
21.03.2011, 11:44     Точки в многоугольнике #11
Посмотри на трапецию ABCD на рисунку
Точки в многоугольнике
Чтобы найти ее площадь (школьная формула S = 1/2 (a+b)h = lh)
h = x1-x2
l = (y1+y2)/2

Поэтому сначала минус, а потом плюс
Yandex
Объявления
21.03.2011, 11:44     Точки в многоугольнике
Ответ Создать тему
Опции темы

Текущее время: 22:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru