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

Простая геометрия - C++

Восстановить пароль Регистрация
 
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
11.06.2013, 21:57     Простая геометрия #1
Недавно решал пачку задач на геометрию, но с одной не справился, даже сейчас не выходит.

Постановка:
Дан выпуклый многоугольник (т.е. все внутренние углы не больше 180 градусов) и прямая. Прямая режет многоугольник на две части (одна из них может оказаться пустой). Какий площади у этих частей?

Входные данные
В первой строке записано число N (2 < N < 51) - количество вершин многоугольника. Далее в N строках заданы вершины своими координатами в порядке обхода по или против часовой стрелки. Возможно, что три или более точек лежит на одной прямой. В последних двух строках записаны координаты двух различных точек по которым проходит разрез. Все координаты задаются через пробел вещественными числами по модулю не превосходящими 10000. Количество знаков после запятой не превосходит 5. Вероятно, что разрез не пройдет через многоугольник.

Выходные данные
Выведите S1 и S2 через пробел с 5 знаками после запятой, S1 >= S2.

Ввод
4
0 0
0 1
1 1
1 0
0.5 0
0.5 1
Вывод
0.50000 0.50000

Решал я её банально -- просто шёл по всем сторонам многоугольника и набирал в список нового многоугольника пройдённые вершины, в случае если на пути мы пересекли прямую нечётное число раз, в случае пересечения заносим ещё и точку пересечения. После чего считаем новую площадь итд.

Result - 46/70, проходит половину тестов.

Вот мои наработки :
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <bitset>
 
using namespace std;
 
bool in_segment(double x, double y, double x1, double y1, double x2, double y2) {
    return (abs ((y1 -y2) * (x1 - x) -(y1 - y) * (x1 - x2)) <= 1e-8  && 
            x >= min(x1, x2) && x <= max(x1, x2) && 
            y >= min(y1, y2) && y <= max(y1, y2));
}
 
pair < bool, pair <double, double> > solv(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
    if ((y2-y1)*(x3-x4) == (y4-y3)*(x1-x2))
        return make_pair(false, make_pair(0.0, 0.0));
    double k = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)) / ((x2-x1)*(y4-y3)-(y2-y1)*(x4-x3));
    double xx = x1+k*(x2-x1);
    double yy = y1+k*(y2-y1);
    return make_pair(in_segment(xx, yy, x1, y1, x2, y2), make_pair(xx, yy));
}
 
 
double arr(vector <double> x, vector <double> y) {
    double ans = 0;
    for (int i = 0; i < x.size() - 1; ++i) 
        ans += (x[i+1] - x[i]) * (y[i+1] + y[i]);
    return abs(ans) / 2.0;
}
 
int main() {
    freopen ("input.txt", "rt", stdin);
    freopen ("output.txt", "wt", stdout);
    int n;
    cin >> n;
    vector <double> x(n+1), y(n+1);
    double x1, y1, x2, y2;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &x[i], &y[i]);
    x[n] = x[0];
    y[n] = y[0];
    double total = arr(x, y);
    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    pair < bool, pair <double, double> > t;
    vector <double> normx, normy;
    bool flag = true;
    for (int i = 0; i < n; ++i) {
        t = solv(x[i], y[i], x[i + 1], y[i + 1], x1, y1, x2, y2);
        if (flag) {
            normx.push_back(x[i]);
            normy.push_back(y[i]);
        }
        if (t.first) {
            normx.push_back(t.second.first);
            normy.push_back(t.second.second);
            flag = !flag;
        }
    }
    normx.push_back(normx[0]);
    normy.push_back(normy[0]);
    double s1 = arr(normx, normy);
    printf("%.6lf %.6lf", max(s1, total - s1), min(s1, total - s1));
    return 0;
}
Добавлено через 3 минуты
Функции - arr - площадь многоугольника.
Solv - возвращает true как первый аргумент пары, если пересеклась прямая по двум точкам (x3,y3,x4,y4), с отрезком x1, y1, x2, y2. И если точка пересечения имеется, то как второй аргумент -- её координаты.
in_segment - проверка принадлежности точки отрезку.

Добавлено через 6 минут
подправил
C++
1
 if ((y2-y1)*(x3-x4) == (y4-y3)*(x1-x2))
на
C++
1
if (abs((y2-y1)*(x3-x4) - (y4-y3)*(x1-x2)) <= 1e-8)
но опять 46 тестов

Добавлено через 5 часов 58 минут
up !

Добавлено через 1 час 48 минут
ну давайте, ребят, help, что угодно, хотя бы идеи новые подкиньте !
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2013, 21:57     Простая геометрия
Посмотрите здесь:

C++ геометрия
1) массивы 2)геометрия C++
Геометрия(треугольник) C++
Геометрия в С++. C++
Вычислительная геометрия на С C++
C++ Геометрия и графика
C++ Геометрия
C++ геометрия

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
12.06.2013, 18:44  [ТС]     Простая геометрия #2
Уии!! Народ, почти запилил из 70 тестов проходит 68
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <bitset>
 
using namespace std;
 
double px, py;
const double eps = 1e-8;
 
bool intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
    if (abs((y2 - y1) * (x3 - x4) + (y4 - y3) * (x2 - x1)) <= eps)
        return false;
    double k = ((x4 - x3) * (y1 - y3) + (y4 - y3) * (x3 - x1)) / ((x2 - x1) * (y4 - y3) + (y1 - y2) * (x4 - x3));
    px = x1 + k * (x2-x1);
    py = y1 + k * (y2-y1);
    return (px >= min(x1, x2) && px <= max(x1, x2) && py >= min(y1, y2) && py <= max(y1, y2));
}
 
 
double arr(vector <double> & x, vector <double> & y) {
    double ans = 0;
    for (int i = 0; i < x.size() - 1; ++i) 
        ans += (x[i+1] - x[i]) * (y[i+1] + y[i]);
    return abs(ans) / 2.0;
}
 
int main() {
    freopen ("input.txt", "rt", stdin);
    freopen ("output.txt", "wt", stdout);
    int n;
    scanf("%d", &n);
    vector <double> x(n+1), y(n+1);
    double x1, y1, x2, y2;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &x[i], &y[i]);
    x[n] = x[0];
    y[n] = y[0];
    double total = arr(x, y);
    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    vector <double> normx, normy;
    bool flag = true;
    for (int i = 0; i < n; ++i) {
        if (flag) {
            normx.push_back(x[i]);
            normy.push_back(y[i]);
        }
        if (intersect(x[i], y[i], x[i + 1], y[i + 1], x1, y1, x2, y2)) {
            if ((abs(px - normx[normx.size()-1]) <= eps && abs(py - normy[normy.size()-1]) <= eps))
                continue;
            normx.push_back(px);
            normy.push_back(py);
            flag = !flag;
        }
    }
    normx.push_back(normx[0]);
    normy.push_back(normy[0]);
    double s1 = arr(normx, normy);
    printf("%.15lf %.15lf", max(s1, total - s1), min(s1, total - s1));
    return 0;
}
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.09.2013, 15:45  [ТС]     Простая геометрия #3
Решил. Была потеря точности. Прошла на CXX (MINGW C++) Вот с таким кодом.
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
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <bitset>
#include <limits>
#include <ctime>
#include <deque>
#include <iterator>
#include <sstream>
#include <stdio.h>
 
using namespace std;
 
long double A, B, C;
long double eps = 1e-8;
 
long double det (long double a, long double b, long double c, long double d) {
    return a * d - c * b;
}
 
vector <long double> sx, sy;
 
void side(long double x, long double y) {
    if (A * x + B * y + C < eps) sx.push_back(x), sy.push_back(y);
}
 
long double px, py;
 
bool intersect(long double x1, long double y1, long double x2, long double y2) {
    long double A2 = y1 - y2;
    long double B2 = x2 - x1;
    long double C2 = - (A2 * x1 + B2 * y1);
    long double zn = det (A, B, A2, B2);
    if (fabs(zn) < eps || 
        (fabs (det (A, B, A2, B2)) < eps &&
         fabs (det (A, C, A2, C2)) < eps &&
         fabs (det (B, C, B2, C2)) < eps)) 
        return false;
    px = - det (C, B, C2, B2) / zn;
    py = - det (A, C, A2, C2) / zn;
    return true;
}
 
long double arr(const vector <long double> & x, const vector <long double> & y) {
    if (x.size() < 4)
        return 0.0;
    long double ans = 0;
    for (int i = 0; i < x.size() - 1; ++i) 
        ans += (x[i+1] - x[i]) * (y[i+1] + y[i]);
    return fabs(ans) / 2.0;
}
 
void scan_line_coords(){
    long double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    A = y1 - y2;
    B = x2 - x1;
    C = - (A * x1 + B * y1);
}
 
int main() {
    int n;
    cin >> n;
    vector <long double> x(n+1), y(n+1);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
    x[n] = x[0], y[n] = y[0];
    scan_line_coords();
    double arr1 = arr(x, y);
    for (int i = 0; i < n; ++i) {
        side(x[i], y[i]);
        if (intersect(x[i], y[i], x[i+1], y[i+1]))
            side(px, py);
        side(x[i+1], y[i+1]);
    }
    if (sx.size() > 0)
        sx.push_back(sx[0]), sy.push_back(sy[0]);
    double arr2 = arr(sx, sy);
    arr1 -= arr2;
    if (arr1 < arr2)
        swap(arr1, arr2);
    printf("%.15lf %.15lf", arr1, arr2);
    return 0; 
 }
Yandex
Объявления
02.09.2013, 15:45     Простая геометрия
Ответ Создать тему

Метки
геометрия, многоугольник, отсечение
Опции темы

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