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

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

Восстановить пароль Регистрация
 
koks90210
Сообщений: n/a
07.10.2013, 14:06     Решение не проходит один тест. Задача: разрезанный прямоугольник #1
Здравствуйте!
Задача состоит в следующем:

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

Формат входных данных
Сначала на вход программы поступают два положительных числа 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++ Задача на строки(поправьте решение)
C++ В цикле почему-то проходит по условию только один раз
В с++ такая задача: проверить, все ли столбцы матрицы содержат хотя бы один положительный элемент. C++
C++ Программа не проходит тест на acmp.ru
Программа на контестере проходит только 1 тест из 9. Можете объяснить, в чем моя ошибка и как ее исправить! C++
Задача на ветвления (С++) Выяснить, верно ли, что первый прямоугольник целиком содержится во втором C++
C++ Помещается ли один прямоугольник в другом?
C++ Задача прямоугольник

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

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

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