Прямоугольники и гвозди (C++)

@Legolas777 · Регистрация: 28.01.2016

Студворк — интернет-сервис помощи студентам

Не могу понять суть задачи, помогите пожалуйста)
На координатной плоскости задано N прямоугольников – кождый парой противоположных вершин, стороны которых параллельны осям координат, а координаты вершин – целые числа из промежутка [-50, 50]. Какое наибольшее количество прямоугольников можно прибить к плоскости одним гвоздём? Прямоугольник считается прибитым, если гвоздь забит во внутреннюю точку прямоугольника.

Входные данные

В первой строке записано одно число N. Далее находится N строк по 4 числа – координаты одной из диагоналей прямоугольника.

Выходные данные

Одно число – наибольшее количество прямоугольников, которое можно прибить одним гвоздём.

Входные данные Выходные данные
4 3
-9 -11 -13 12
3 -3 -10 9
13 9 -12 10
9 6 -10 -8
https://www.e-olymp.com/ru/con... lems/93413

@zss · 24.05.2018, 13:55

Нужно найти точку, принадлежащую наибольшему количеству прямоугольников.
Поэтому
1. находим координаты прямоугольника, в который вписаны все остальные прямоугольники

2. проходим по всем точкам этого прямоугольника, считаем количество прямоугольников,
которым принадлежит эта точка и находим максимум и его координаты.

@MansMI · 24.05.2018, 14:01

Сообщение от Legolas777

целые числа из промежутка [-50, 50]
.....
если гвоздь забит во внутреннюю точку прямоугольника

т.е точек всего то 99² и прямоугольники с шириной/высотой=1 не интересны

@Legolas777 · 24.05.2018, 15:16 **[ТС]**

zss, я не могу понять саму суть данных, -9 = х; -11 = у так же или я что то путаю?

Добавлено через 7 минут
zss, есть ли у вас возможность наглядно показать как это сделать, буду очень благодарен

@slava_psk · 24.05.2018, 15:37

Если просмотреть весь массив координат вершин, то можно найти границы области xmin,xmax ymin, умах.
1.Разбиваете всю это область сеткой xi,yi
2. Для каждой точки xi,yi определяете количество прямоугольников в которые она попадает. И выбирает тем самым точку с максимальным попаданием.

Если никто не напишет, завтра я могу.

@Legolas777 · 24.05.2018, 16:00 **[ТС]**

slava_psk, огромное спасибо за ответ, если будет такая возможность и не справлюсь сам буду очень благодарен вашей помощи!)

@Просто Саша · 24.05.2018, 16:49

Сообщение от zss

Нужно найти точку, принадлежащую наибольшему количеству прямоугольников.
Поэтому
1. находим координаты прямоугольника, в который вписаны все остальные прямоугольники
2. проходим по всем точкам этого прямоугольника, считаем количество прямоугольников,
которым принадлежит эта точка и находим максимум и его координаты.

Думаю, что можно проще, хотя этот алгоритм подходит только для целочисленных вершин.
1) Просто тупо вколачиваем гвоздь в узел (0, 0) и считаем число прибитых прямоугольников.
2) Продолжаем вбивать гвозди в каждый целочисленный узел, пока не дойдем до узла с координатой (50, 50).
3) По ходу определяем текущее максимальное прибитое число прямоугольников.
4) После того как гвоздь вбит в узел (50, 50), наш максимум должен быть определен.

@slava_psk · 25.05.2018, 11:27

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
#include <cstdlib> 
#include <iostream> 
#include <string>
 
using std::cout;
using std::cin;
using std::endl;
 
int main()
{
double x1[] = { -9, 3, 13, 9}; 
double x2[] = { -13, -10, -12, -10}; 
double y1[] = { -11, -3, 9, 6};
double y2[] = { 12, 9, 10, -8},tmp;
double xmin,xmax,ymin,ymax,xi,yj,x0,y0;
int i,ic,ic_max;
   setlocale(0, "");
   // Упорядочивание массивов координат
   for(i=0;i<4;i++)
   {
   if(x1[i]>x2[i])
   {
   tmp=x1[i];
   x1[i]=x2[i];
   x2[i]=tmp;
   }
   if(y1[i]>y2[i])
   {
   tmp=y1[i];
   y1[i]=y2[i];
   y2[i]=tmp;
   }
   }
   //Поиск границ области
   xmin=x1[0]; 
   xmax=x2[3];
   ymin=y1[0]; 
   ymax=y1[3];
   for(i=0;i<4;i++)
   {
   if(x1[i]<xmin) 
   xmin=x1[i];
   if(x2[i]>xmax) 
   xmax=x2[i];
   if(y1[i]<ymin) 
   ymin=y1[i];
   if(y2[i]>ymax) 
   ymax=y2[i];
   }
   //Поиск точки для гвоздя
   xi=xmin-0.5;
       ic_max=0;
           do{
           xi=xi+0.5;
           yj=ymin-0.5;
           ic=0;
           do{
               yj=yj+0.5;
               //Проверка попадания точки 
               ic=0;
               for(i=0;i<4;i++)
               {
                if(xi>x1[i] && xi<x2[i] && yj>y1[i] && yj<y2[i]) ic++;
                if(ic>ic_max) {ic_max=ic;x0=xi;y0=yj;}
               }
              } while (yj<ymax);
       } while (xi<xmax);
            cout<<"Можно прибить "<<ic_max<<" прямоугольника "<<endl;
            cout<<"В точку "<<x0<<" "<<y0<<endl;
   system("pause"); // Только для тех, у кого MS Visual Studio
}

@Legolas777 · 25.05.2018, 13:21 **[ТС]**

slava_psk, массив не статический а динамический должен быть
Здесь нужно в на координатной площади посщитать для каждного сектора количество прямоуольников
[-13;12] первая координата и первый прямоугольник в отсеке [-x;+y]
[-12;10]
[-10; 9 ] в отсеке [-x;+y] получилось 3 прямоугольника т.е. 3

в отсеке [+x;+y] получилось 2 [13;9] и [9;6]
в отсеке [-x;-y] получилось 2 [-10;-8] и [-9;-11]
в отсеке [+x;-y] получился 1 [3;-3]

каким способом можна реализовать даное решение

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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
 
int main()
{   
    int mas[50][50], n, i = 0, j = 0, xmin , xmax, ymin, ymax;
    
    cout << " Vvedit rozmir n = ";
    cin >> n;
    cout << "Vvedit dani rozmiron [" << n <<"][" << n <<"]" << endl;
    
    for (i = 0; i < n; i++ )
        for (j = 0; j < n; j++ )
            cin >>mas[i][j];
    
    xmin = mas [0][0];
    xmax = mas [0][0];
    for (i = 0; i < n; i+=2 )
        for (j = 0; j < n; j+=2 )
            {
                if (mas[i][j] < xmin) xmin = mas[i][j];
                if (mas[i][j] > xmax) xmax = mas[i][j];
            }
    
    ymin = mas [0][1];
    ymax = mas [0][1];
    for (i = 0; i < n; i+=2 )
        for (j = 1; j < n; j+=2 )
            {
                if (mas[i][j] < ymin) ymin = mas[i][j];
                if (mas[i][j] > ymax) ymax = mas[i][j];
            }
    
    
    cout << "Xmax = " << xmax << endl << "Xmin = " << xmin << endl;
    cout << "Ymax = " << ymax << endl << "Ymin = " << ymin << endl;
    
 
    return 0;
}

Добавлено через 1 час 35 минут
Вот пример к моему предположению но на проверке результат 30% из 100%
Помогите пожалуйста найти ошибку

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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
 
int main()
{   
    int mas[50][50], n, i = 0, j = 0, xy1 = 0, xy2 = 0, xy3 = 0, xy4 = 0;
    
    cout << " Vvedit rozmir n = ";
    cin >> n;
    cout << "Vvedit dani rozmiron [" << n <<"][" << n <<"]" << endl;
    
    for (i = 0; i < n; i++ )
        for (j = 0; j < n; j++ )
            cin >>mas[i][j];
    
    
    for (i = 0; i < n; i++ )
        {
            for (j = 0; j < n; j+=2 )
                {
                    if (mas[i][j] < 0 && mas[i][j+1] > 0) xy1++;
                    if (mas[i][j] > 0 && mas[i][j+1] > 0) xy2++;
                    if (mas[i][j] < 0 && mas[i][j+1] < 0) xy3++;
                    if (mas[i][j] > 0 && mas[i][j+1] < 0) xy4++;
                }
        }
        
    if (xy1 > xy2 & xy1 > xy3 & xy1 > xy4) cout << xy1 << endl;
    if (xy2 > xy1 & xy2 > xy3 & xy2 > xy4) cout << xy2 << endl;
    if (xy3 > xy1 & xy3 > xy2 & xy3 > xy4) cout << xy3 << endl;
    if (xy4 > xy1 & xy4 > xy2 & xy4 > xy3) cout << xy4 << endl;
 
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Legolas777 0 / 0 / 0 Регистрация: 28.01.2016 Сообщений: 4

	Прямоугольники и гвозди (C++) 24.05.2018, 13:40. Показов 1323. Ответов 8 Метки нет (Все метки) Не могу понять суть задачи, помогите пожалуйста) На координатной плоскости задано N прямоугольников – кождый парой противоположных вершин, стороны которых параллельны осям координат, а координаты вершин – целые числа из промежутка [-50, 50]. Какое наибольшее количество прямоугольников можно прибить к плоскости одним гвоздём? Прямоугольник считается прибитым, если гвоздь забит во внутреннюю точку прямоугольника. Входные данные В первой строке записано одно число N. Далее находится N строк по 4 числа – координаты одной из диагоналей прямоугольника. Выходные данные Одно число – наибольшее количество прямоугольников, которое можно прибить одним гвоздём. Входные данные Выходные данные 4 3 -9 -11 -13 12 3 -3 -10 9 13 9 -12 10 9 6 -10 -8 https://www.e-olymp.com/ru/con... lems/93413 0

@zss Модератор 13773 / 10966 / 6491 Регистрация: 18.12.2011 Сообщений: 29,244
	24.05.2018, 13:55
	Нужно найти точку, принадлежащую наибольшему количеству прямоугольников. Поэтому 1. находим координаты прямоугольника, в который вписаны все остальные прямоугольники 2. проходим по всем точкам этого прямоугольника, считаем количество прямоугольников, которым принадлежит эта точка и находим максимум и его координаты. 0

@Legolas777 0 / 0 / 0 Регистрация: 28.01.2016 Сообщений: 4
	24.05.2018, 15:16 [ТС]
	zss, я не могу понять саму суть данных, -9 = х; -11 = у так же или я что то путаю? Добавлено через 7 минут zss, есть ли у вас возможность наглядно показать как это сделать, буду очень благодарен 0

@slava_psk 692 / 489 / 251 Регистрация: 10.06.2016 Сообщений: 2,337
	24.05.2018, 15:37
	Если просмотреть весь массив координат вершин, то можно найти границы области xmin,xmax ymin, умах. 1.Разбиваете всю это область сеткой xi,yi 2. Для каждой точки xi,yi определяете количество прямоугольников в которые она попадает. И выбирает тем самым точку с максимальным попаданием. Если никто не напишет, завтра я могу. 0

@Legolas777 0 / 0 / 0 Регистрация: 28.01.2016 Сообщений: 4
	24.05.2018, 16:00 [ТС]
	slava_psk, огромное спасибо за ответ, если будет такая возможность и не справлюсь сам буду очень благодарен вашей помощи!) 0