Помогите пожалуйста составить программу на СИ++. Заранее всем БЛАГОДАРЕН!
Подсказка: "Где-то видел что решается по формуле Пика! "
Подсказка: "Где-то видел что решается по формуле Пика! "
> Вообще-то по формуле Пика высчитывается площадь
Вычислим площадь по другой формуле, посчитаем количество точек на границе, и из формулы Пика выведем количество внутренних точек:
#include
using namespace std;
int gcd(int a, int b) {
while (b) {
int m = a % b;
a = b;
b = m;
}
return a;
}
int main() {
int n;
long long fx, fy, x0, y0, x1, y1, s = 0, np = 0;
cin >> n >> fx >> fy;
x0 = fx;
y0 = fy;
for (int i = 0; i < n - 1; ++i) {
cin >> x1 >> y1;
np += gcd(x0 > x1? x0 - x1 : x1 - x0, y0 > y1? y0 - y1 : y1 - y0);
s += x0 * y1 - x1 * y0;
x0 = x1;
y0 = y1;
}
np += gcd(x0 > fx? x0 - fx : fx - x0, y0 > fy? y0 - fy : fy - y0);
s += x0 * fy - fx * y0;
cout << ((s > 0? s : -s) - np + 2) / 2 << endl;
return 0;
}
Вообще-то по формуле Пика высчитывается площадь, а у Вас другая задача.
Кроме банального определения области проверяемых точек и определения их положения относительно прямых, образованных соединениями вершин многоугольника, ничего не вижу пока!