Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.06.2013, 21:57. Просмотров 709. Ответов 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, что угодно, хотя бы идеи новые подкиньте !
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2013, 21:57
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Простая геометрия (C++):

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

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

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

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

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

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

2
Ternsip
663 / 191 / 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;
}
0
Ternsip
663 / 191 / 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; 
 }
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2013, 15:45
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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