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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

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

11.06.2013, 21:57. Просмотров 650. Ответов 2

Недавно решал пачку задач на геометрию, но с одной не справился, даже сейчас не выходит.

Постановка:
Дан выпуклый многоугольник (т.е. все внутренние углы не больше 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++
Здравствуйте. Помогите решить задчу: &quot;Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n (n&gt;=3)...

геометрия - C++
Решите пожалуйста, ребят ( Решить задачу, используя структуру point для хранения координат точки: Найти такую точку, сумма расстояний...

Геометрия - C++
Г Е О М Е Т Р И Ч Е С К И Е З А Д А Ч И -&gt; Здесь выкладываем условия и/или решения геометрических задач &lt;-

Геометрия в С++ - C++
Даны две вершины прямоугольного треугольника A,B,так же известны угол A и угол B.Нужно найти третью вершину треугольника.Пробывал решать...

геометрия - C++
:help::help: Даны действительные числа x, y. Вычислить расстояние от точки плоскости с координатами (x, y) до границы квадрата * с...

Вычислительная геометрия на С - C++
Заданы координаты N точек. Определить те две точки, проведенная через которые прямая делит имеющиеся точки пополам.

Геометрия(треугольник) - C++
Даны два угла треугольника (в градусах). Определить, существует ли такой треугольник, и если да, то будет ли он прямоугольным.

1) массивы 2)геометрия - C++
Здравствуйте! Помогите пожалуйста решить задачи, очень надо! 1)Определить частоты вхождения в число N! (N&lt;=100) цифр, из которых...

Геометрия и графика - C++
Решить задачу и отобразить решение графически на экране. Исходные данные прочитать из текстового файла. Задача: На плоскости задано...

чистая геометрия, но заваливается( - C++
http://acm.timus.ru/problem.aspx?space=1&amp;num=1084 Козла пустили в квадратный огород и привязали к колышку. Колышек воткнули точно в...

Геометрия. Симметричная точка - C++
Доброго времени суток!:) Задача : Дана прямая, проходящая через две различные точки (x1,y1) и (x2,y2). Найдите точку, симметричную...

Вычислительная геометрия, путь по сфере - C++
Нужна помощь с задачкой:( Яблоко имеет форму идеального шара радиуса R1. В центре яблока находится сердцевина также имеющая форму шара...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
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     Простая геометрия
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru