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

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

Войти
Регистрация
Восстановить пароль
 
koks90210
#1

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

07.10.2013, 14:06. Просмотров 665. Ответов 0
Метки нет (Все метки)

Здравствуйте!
Задача состоит в следующем:

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

Формат входных данных
Сначала на вход программы поступают два положительных числа X и Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.
Далее вводится целое число N — количество разрезов (1≤N≤200). Затем описываются сами разрезы. Каждый разрез делался вдоль некоторой прямой. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).
Все входные данные (кроме N) – вещественные числа, заданы с двумя знаками после десятичной точки и не превышают 104. Никакие две прямые не совпадают между собой и не содержат сторон прямоугольника. Каждый разрез проходит через точки внутри исходного прямоугольника.

Формат выходных данных
Выведите одно целое число — количество частей исходного прямоугольника, имеющих треугольную форму.
_____________________________________________________________________________________________________

Я написала код, который проходит 32 из 33 тестов, и не могу понять, в чем же ошибка. Что за один тест такой. Помогите, пожалуйста, понять, в чем ошибка, где недочет.

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
 
using namespace std;
 
typedef unsigned int uint;
 
const double EPS = 1e-9;
 
struct Point {
    double x,y;
    bool operator==(Point b){
        return (this->x == b.x && this->y == b.y);
    }
};
 
struct Line {
    double a,b,c;
};
 
Point bl, tr;
Line sLeft, sTop, sRight, sBottom;
 
bool between(double value, double left, double right){
    if(right < left){
        return (value <= left && value >= right);
    }
    return (value <= right && value >= left);
}
 
double det (double a, double b, double c, double d) {
    return a * d - b * c;
}
 
bool intersect(Line m, Line n, Point & res) {
    double zn = det (m.a, m.b, n.a, n.b);
    if (abs (zn) == 0)
        return false;
    res.x = - det (m.c, m.b, n.c, n.b) / zn;
    res.y = - det (m.a, m.c, n.a, n.c) / zn;
    return true;
}
 
bool intersectInRect(Line line1, Line line2, Point & res){
    Point p;
    if(!intersect(line1, line2, p)){
        return false;
    }
    if(between(p.x, 0, tr.x) == false || between(p.y, 0, tr.y ) == false){
        return false;
    }
    res = p;
    return true;
}
 
Point genPoint(double x, double y){
    Point p;
    p.x = x;
    p.y = y;
    return p;
}
 
vector< Point > pDict;
vector<vector< uint >> pGraph;
 
uint getPIndex( Point p ){
    for(uint i=0; i<pDict.size(); ++i){
        if(pDict[i] == p){
            return i;
        }
    }
}
 
void addToPD( Point p ){
    for(uint i=0; i<pDict.size(); ++i){
        if(pDict[i] == p){
            return;
        }
    }
    
    pDict.push_back(p);
    pGraph.push_back( *(new vector<uint>) );
}
 
void addNeighbour( Point to, Point what ){
    // 'to' and 'what' are in pDict
    uint ti = getPIndex( to );
    uint tw = getPIndex( what );
    if(find(pGraph[ti].begin(), pGraph[ti].end(), tw) == pGraph[ti].end()){
        pGraph[ ti ].push_back( tw );
    }
}
 
bool pointOrderPred(Point const & p1, Point const & p2) {
    return p1.x < p2.x;
}
bool pointOrderByYPred(Point const & p1, Point const & p2) {
    return p1.y < p2.y;
}
 
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    bl.x = 0; bl.y = 0;
    cin >> tr.x >> tr.y;
 
    sLeft.a = 1; sLeft.b = 0; sLeft.c = 0;  
    sTop.a = 0; sTop.b = 1; sTop.c = -tr.y; 
    sRight.a = 1; sRight.b = 0; sRight.c = -tr.x;   
    sBottom.a = 0; sBottom.b = 1; sBottom.c = 0;
 
    uint N;
    cin >> N;
 
    // initial rectangle lines
    vector<Line> lines;
    lines.push_back(sLeft);
    lines.push_back(sTop);
    lines.push_back(sBottom);
    lines.push_back(sRight);
 
    // read line
    for(uint i=0; i<N; ++i){
        vector<Point> cLinePoints;
 
        Line line;
        cin >> line.a >> line.b >> line.c;
 
        // add line to vector
        lines.push_back( line ); 
    }
 
    for(uint i=0; i<lines.size(); ++i){
        // if line is vertical, we order all points on it by y only
        
        vector<Point> linePoints;
        for(uint j=0; j<lines.size(); ++j){
            if(i==j) continue;
            
            Point p;
            if(intersectInRect(lines[i], lines[j], p)){
                if(find(linePoints.begin(), linePoints.end(), p) == linePoints.end()){
                    linePoints.push_back(p);
                }
            }
        }
        
        // sort all points on line according to extraOrder
        bool eo = false;
        if(lines[i].b == 0){
            eo = true;
        }else{
            if(abs( lines[i].a / lines[i].b ) > 1){
                eo = true;
            }
        }
 
        if(eo){
            sort(linePoints.begin(), linePoints.end(), pointOrderByYPred);
        }else{
            sort(linePoints.begin(), linePoints.end(), pointOrderPred);
        }
 
        // first, add them
        for(uint x=0; x<linePoints.size(); ++x){
            addToPD(linePoints[x]);
        }
 
        // now we can use addNeighbour()
        for(uint x=0; x<linePoints.size(); ++x){
            if(x>0){
                addNeighbour( linePoints[x], linePoints[x-1] );
            }
            if(x<(linePoints.size()-1)){
                addNeighbour( linePoints[x], linePoints[x+1] );
            }
        }
    }
 
    uint triangles = 0;
    // now walking the vertices
    for(uint i = 0; i<pDict.size(); ++i){
        
        
        // now we looking _any_ two neighbours
        for(uint x=0; x<pGraph[i].size(); ++x){
            uint nv1 = pGraph[i][x];
 
            for(uint y=0; y<pGraph[i].size(); ++y){
                if(x == y) continue;
                uint nv2 = pGraph[i][y];
                // ...and if there is a straight line between these neighbours
                if( find(pGraph[nv1].begin(), pGraph[nv1].end(), nv2) != pGraph[nv1].end() &&
                    find(pGraph[nv2].begin(), pGraph[nv2].end(), nv1) != pGraph[nv2].end()
                ){
                    // ...it is a triangle here!
                    //cout << "Triangle with: " << i << ", " << nv1 << ", " << nv2 << endl;
                    ++triangles;
                }
            }
        }
 
    }
 
    cout << (uint) (triangles / 6) << endl; 
}
Добавлено через 19 часов 39 минут
Задача с сайта http://informatics.mccme.ru под номером 34, и не проходит 18 тест. может кто-то делал её. помогите пожалуйста.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.10.2013, 14:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Решение не проходит один тест. Задача: разрезанный прямоугольник (C++):

Программа не проходит тест на acmp.ru - C++
http://********/index.asp?main=task&amp;id_task=446 На хоккейном стадионе в одном большом городе расположено большое прямоугольное табло. Оно...

Сбор черники. Программа не проходит 11 тест - C++
Текст задачиСбор черники (Время: 1 сек. Память: 16 Мб Сложность: 17%) В фермерском хозяйстве в Карелии выращивают чернику. Она...

Антагонистические игры двух лиц, програмама не проходит 3 тест - C++
Задача: Теория игр (Время: 1 сек. Память: 16 Мб Сложность: 28%) Одним из интересных объектов, изучаемых в теории игр, являются так...

Программа на контестере проходит только 1 тест из 9. Можете объяснить, в чем моя ошибка и как ее исправить! - C++
Объясните, в чем моя ошибка в решении задачи. Условие: 103. Подсчет войск ограничение времени на тест: 0.5 сек. ...

В цикле почему-то проходит по условию только один раз - C++
Задача такая: Дан одномерный массив и натуральных чисел. Удалить из него все тройки подряд идущих равных чисел, и вывести размер...

Помещается ли один прямоугольник в другом? - C++
дано дійсні додатні числа a b c d . З’ясувати, чи можна пря- мокутник зі сторонами a b, вмістити всередині прямокутника зі сто- ронами...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2013, 14:06
Привет! Вот еще темы с ответами:

Задача прямоугольник - C++
Задан целочисленный прямоугольный массив MxN. Необходимо определить прямоугольную область данного массива, сумма элементов которого...

Задача не проходит тест - Java SE
Добрый день. Есть такая простая задача. /* Нужно добавить в программу новую функциональность Задача: У каждой кошки есть имя и...

Не проходит тест - C#
Не проходит тест на соответствие. Вроде пишет, что Результат Сообщение: Ошибка в Assert.AreEqual. Ожидается: &lt;System.String&gt;....

Программа не проходит тест - Free Pascal
Нужно было сделать программу для определения, является ли десятичная дробь конечной при переводе в двоичную СС. Если да, то перевести и...


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

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

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