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

Задача "Салфетки" - C++

Восстановить пароль Регистрация
 
triadec_96
 Аватар для triadec_96
11 / 11 / 0
Регистрация: 27.12.2012
Сообщений: 433
Завершенные тесты: 1
11.11.2013, 22:24     Задача "Салфетки" #1
Задача:
На квадратный стол размером NХN раскладывают разноцветные прямоугольные салфетки.
Каждая салфетка кладется параллельно сторонам стола , салфетки могут лежать друг на друге и свисать со стола , или даже падать мимо стола.
Салфетка задается координатами углов : левый верхний , правый нижний ( целые числа ) и цветом ( буква)
Левый верхний угол стола имеет координаты 0,0
Какие цвета будут видны на столе когда все салфетки будет разложено .
Входные данные : файл Din.dat
Первая строка число N пропуск число K
Следующие K строк задают салфетки в порядке преподавания
Каждая строка имеет вид: ltrbc (где ltr b - целые числа , с - латинская буква )
Выходные данные : файл Din.res в котором строка букв цветов ( в алфавитном порядке)
Пример:: файл Din.dat
5 5
-1 -1 4 4 R
2 1 2 2 C
1 1 3 2 b
-1 4 6 8 B
6 4 6 6 g
файл Din.res
BRb
Я начал писать эту программу и мой код дошёл до этого вида.
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
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
void main()
{int n,i,j,l[255],t[255],r[255],b[255],id=0,q=0;
        char* ch;
        char* c;
        char* v;
        char a; bool x; float d,s[255];
ifstream f("Din.dat");
f>>n;
f>>n;
while(!f.eof())
{f>>l[id];
f>>t[id];
f>>r[id];
f>>b[id];
f>>ch[id];}
 
for(i=0;i<=id;i++)
{if(l[i]<0) l[i]=0;
if(t[i]>0) t[i]=0;
if(r[i]>n) r[i]=n;
if(b[i]<n*(-1)) b[i]=n*(-1);}
 
for(i=0;i<=id;i++)//площа квадрата=діагональ в квадраті/2
{d=abs(pow(l[i]-r[i],2)+pow(t[i]-b[i],2));
s[i]=d*d/2;}
 
for(i=0;i<=id;i++)
    for(j=i+1;j<=id;j++)
        if((l[j]<r[i]) && (l[j]>l[i]) && (t[j]<t[i]) && (t[j]>b[i])) s[i]-=(abs(pow(l[j]-r[i],2)+pow(t[j]-b[i],2))*abs(pow(l[j]-r[i],2)+pow(t[j]-b[i],2)))/2;
        else if((r[j]<r[i]) && (r[j]>l[i]) && (t[j]>b[j]) && (t[j]<t[i])) s[i]-=(abs(pow(l[i]-r[j],2)+pow(t[j]-b[i],2))*abs(pow(l[i]-r[j],2)+pow(t[j]-b[i],2)))/2;
        else if((r[j]<r[i]) && (r[j]>l[i]) && (b[j]>b[i]) && (b[j]<t[i])) s[i]-=(abs(pow(l[i]-r[j],2)+pow(t[i]-b[j],2))*abs(pow(l[i]-r[j],2)+pow(t[i]-b[j],2)))/2;
        else if((l[j]<r[i]) && (l[j]>l[i]) && (b[j]<t[i]) && (b[j]>b[i])) s[i]-=pow(abs(pow(l[j]-r[i],2)+pow(t[i]-b[j],2)),2)/2;
        else if((l[j]==l[i]) && (t[j]==t[i]) && (r[j]<r[i]) && (b[j]>b[i])) s[i]-=(abs(pow(l[j]-r[j],2)+pow(t[i]-b[j],2))*abs(pow(l[j]-r[j],2)+pow(t[i]-b[j],2)))/2;
        else if((l[i]==l[j]) && (b[j]==b[i]) && (r[j]<r[i]) && (t[j]<t[i])) s[i]-=pow(abs(pow(l[i]-r[j],2)+pow(t[j]-b[i],2)),2)/2;
        else if((r[i]==r[j]) && (b[i]==b[j]) && (l[j]>l[i]) && (t[j]<t[i])) s[i]-=pow(abs(pow(l[j]-r[i],2)+pow(t[j]-b[i],2)),2)/2;
        else if((l[j]>l[i]) && (t[j]<t[i]) && (r[j]<r[i]) && (b[j]>b[i])) s[i]-=s[j];
        else if((l[j]<l[i]) && (t[j]>t[i]) && (r[j]>r[i]) && (b[j]<b[i])) s[i]=0;
 
        n=0;
        for(i=0;i<=id;i++)
            if(s[i]>0) {c[n]=ch[i];n++;}
 
n=0;
    for(i=0;i<=n;i++)
    {a=c[i];x=0;
        for(j=i+1;j<=n;j++)
            if(a==c[j]) x=1;
        if (x==0)
        {v[q]=c[i];
        q++;}
    }
 
        ofstream ff("Din.txt");
        ff<<v;
        ff.close();
 
}
Но я немного наптупил и забыл учесть тот факт,что салфетку могут положить мимо стола и забыл за число k 9вместо него у меня счётчик id).
В 2012 ВС выбивало ошибку при считывании ch[id].Но когда я запустил эту программу в ВС 2010,то выбивало ошибку на каждом "pow",хотя math.h был подключен.
Ещё ребята смеялись,когда увидили мой код и сказали,что весь код состоит с "четырёх строк".
Напишите пожалуйста алгоритм получше моего.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
11.11.2013, 23:05     Задача "Салфетки" #2
Цитата Сообщение от triadec_96 Посмотреть сообщение
C++
1
2
f>>n; 
f>>n;
Во второй раз наверно надо писать пресловутое K.

Цитата Сообщение от triadec_96 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
while(!f.eof()) 
{
f>>l[id];
 f>>t[id];
 f>>r[id];
 f>>b[id];
 f>>ch[id];
}
id в цикле не меняется, равняясь постоянно 0. Поэтому все данные записываются только в первую ячейку каждого масива.

Проверку же на попадание салфетки на стол решить довольно просто - необходимо, чтобы координаты хотя бы одной вершины салфетки находились в поле стола.
Функция проверки на попадание на стол:
C++
1
2
3
4
5
6
7
8
bool Check(int x,int y,int x1,int y1)
{
 if(((x>0)&&(x<N))&&((y>0)&&(y<N))) return true;
 if(((x>0)&&(x<N))&&((y1>0)&&(y1<N))) return true;
 if(((x1>0)&&(x1<N))&&((y>0)&&(y<N))) return true;
 if(((x1>0)&&(x1<N))&&((y1>0)&&(y1<N))) return true;
 return false;
}
Вызов функции в программе:
C++
1
2
for(int i=0,i<K;i++)
 if(Check(l[i],t[i],r[i],b[i])) {салфетка на столе - записываем ее цвет в файл}
Как то так - куда проще и меньше кода. Если же надо еще учитывать и наложение салфеток друг на друга, то задача станет куда сложнее .
triadec_96
 Аватар для triadec_96
11 / 11 / 0
Регистрация: 27.12.2012
Сообщений: 433
Завершенные тесты: 1
11.11.2013, 23:23  [ТС]     Задача "Салфетки" #3
Цитата Сообщение от RQdan Посмотреть сообщение
Сообщение от triadec_96
Код C++
1
2
f>>n;
f>>n;
Во второй раз наверно надо писать пресловутое K.
Это я понял после того,как прочитал второй раз задание после написания кода.

Добавлено через 3 минуты
Цитата Сообщение от RQdan Посмотреть сообщение
Как то так - куда проще и меньше кода. Если же надо еще учитывать и наложение салфеток друг на друга, то задача станет куда сложнее .
Наложение салфеток друг на друга в строках 31-41 и с этим у меня проблемы.
Все хохотали когда увидели эту часть кода и сказали что там нечего делать,но не могу понять "как?".Другие методы в голову не приходили.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
12.11.2013, 00:10     Задача "Салфетки" #4
triadec_96,
Цитата Сообщение от triadec_96 Посмотреть сообщение
Наложение салфеток друг на друга в строках 31-41 и с этим у меня проблемы.
Все хохотали когда увидели эту часть кода и сказали что там нечего делать,но не могу понять "как?".Другие методы в голову не приходили.
пришел в голову один вариант: создается двумерный символьный(или целочисельный - неважно) масив color[N][N], который представляет собой поле стола. При падении каждой салфетки ячейки "стола", соответствующие координатам салфетки "окрашиваются"(заполняются соответствующим символом или цифрой).
В конце же проганяем полностью масив и считаем какие цвета остались на столе.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=0;i<K;i++)// проходим весь масив салфеток
 for(int j=l[i];j<=r[i];j++)//проходим координаты по "х" салфетки
  if((j=>0)&&(j<N))//если значение координаты "х" салфетки находится в отрезке 0..N, то обрабатываем дальше
   for(int d=t[i];d<=b[i];d++)//проходим координаты по "у" салфетки
    if((d=>0)&&(d<N))//если значение координаты "у" салфетки находится в отрезке 0..N, то обрабатываем дальше
     color[j][d]=c[i];//точка салфетки находится на столе, и за ее координатами "окрашиваем" поле стола цветом
 
for(int i=0;i<N;i++)//прогон поля стола для нахождения цветов, что остались на столе
 for(int j=0;j<N;j++)
  switch(color[i][j])//определение цвета и обработка(запись в отдельный масив или файл - смотри как тебе надо)
  {
   'r': {обработка кода соотв. цвета}
   'b': {обработка кода соотв. цвета}
    ...
   {обрабатываются все буквы для заданных цветов}
    ...
  }
И в таком случае стает ненужным тот код, что я писал раньше .

Добавлено через 9 минут
P.S. масив color сначала надо будет инициализировать каким-либо нейтральным символом, который не обозначает ни один цвет. Это необходимо в тех случаях, когда на столе будут оставаться области, которые не закрыла ни одна салфетка. Иначе могут возникнуть ошибки.
triadec_96
 Аватар для triadec_96
11 / 11 / 0
Регистрация: 27.12.2012
Сообщений: 433
Завершенные тесты: 1
12.11.2013, 00:49  [ТС]     Задача "Салфетки" #5
Цитата Сообщение от RQdan Посмотреть сообщение
for(int i=0;i<K;i++)// проходим весь масив салфеток
*for(int j=l[i];j<=r[i];j++)//проходим координаты по "х" салфетки
* if((j=>0)&&(j<N))//если значение координаты "х" салфетки находится в отрезке 0..N, то обрабатываем дальше
* *for(int d=t[i];d<=b[i];d++)//проходим координаты по "у" салфетки
* * if((d=>0)&&(d<N))//если значение координаты "у" салфетки находится в отрезке 0..N, то обрабатываем дальше
* * *color[j][d]=c[i];//точка салфетки находится на столе, и за ее координатами "окрашиваем" поле стола цветом
for(int i=0;i<N;i++)//прогон поля стола для нахождения цветов, что остались на столе
*for(int j=0;j<N;j++)
* switch(color[i][j])//определение цвета и обработка(запись в отдельный масив или файл - смотри как тебе надо)
* {
* *'r': {обработка кода соотв. цвета}
* *'b': {обработка кода соотв. цвета}
* * ...
* *{обрабатываются все буквы для заданных цветов}
* * ...
* }
Спасибо огромное)
Алгоритм интересный...не приходится делать сложные математические вычисления (как у моём алгоритме).
Доволи просто,но немножко не могу въехать в него.Но ничего,попытаюсь понять.
Yandex
Объявления
12.11.2013, 00:49     Задача "Салфетки"
Ответ Создать тему
Опции темы

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