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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Почему выдает ошибку http://www.cyberforum.ru/cpp-beginners/thread970404.html
#include <stdio.h> #include <conio.h> #include <stdlib.h> #include <math.h> #include "stdafx.h" #include "windows.h" void main() { float X;
C++ Наследование int main() { setlocale(LC_ALL, "RUS"); Stud FIRST_TRY; FIRST_TRY.set(); exam(FIRST_TRY); FIRST_TRY.get(); system("pause"); return 0; } http://www.cyberforum.ru/cpp-beginners/thread970402.html
В своей области построить из отрезков прямых линий контуры своего объекта C++
Задание: 1. В своей области построить из отрезков прямых линий контуры своего объекта. Для задания координат концов отрезков использовать мировые координаты, которые выбрать следующим образом: максимальная сторона области = 12(м, мм, км). 2. Изменить программу построения объекта, добавив перемещение объекта (области) в заданном направлении на заданную величину. При этом должно происходить...
Проблемы с Аффинным шифром C++
Всем привет! У меня возникли проблемы при реализации программы, которая должна брать исходный текстовый файл и шифровать/дешифровать его Аффинным шифром. Главные проблемы: 1) программа шифрует(не уверен что правильно), но не может дешифровать(скорее всего проблема в моей формуле дешифровки-плохо разбираюсь с модулями) 2) Проблема с русской буквой Я. Доходя до я программа считает что файл...
C++ Построить контуры своей области и заполнить её заданными наклонными линиями http://www.cyberforum.ru/cpp-beginners/thread970390.html
Задание: 1. Построить контуры своей области и заполнить её заданными наклонными линиями.. 2. В своей области построить из отрезков прямых линий контуры заданного объекта. 1 и 2 задание выполнить в двух вариантах: с использованием стандартной функцию line BorlandC и собственной функции, написанной по алгоритму Брезенхейма. 1)Из нижнего левого угла сначала вправо, потом налево. 2)Из нижнего...
C++ Работа с изображениями в GIT Более подходящего раздела для этой темы на форуме не нашел, поэтому пишу здесь. Сегодня зарегистрировался на github и встал такой вопрос. Git хранит не сами файлы, а их изменения. Так вот, если загрузить изображение, то получается, если есть много версий этого изображения, то гит хранит каждую версию? Он ведь не может запоминать изменения для изображений, как для текста, где он просто... подробнее

Показать сообщение отдельно
koks90210
Сообщений: n/a

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

07.10.2013, 14:06. Просмотров 588. Ответов 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 тест. может кто-то делал её. помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 02:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru