многоугольники | C++ для приматов

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов [latex]r[/latex] нужно сделать, чтобы среди полученных частей оказалось [latex]n[/latex] [latex]k[/latex] -угольников?

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

Количество многоугольников [latex]n[/latex].
Количество углов многоугольника [latex]k[/latex].

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

Количество разрезов [latex]r[/latex].

Пример получения двух шестиугольников за 5 разрезов

Код программы

#include <iostream>
using namespace std;
 
int main() {
    int r, n, k;
    cin>>n>>k;
    r=k>3? n*(k-3)-1 : n>1? n-1 : 1;
    cout<<r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, n, k;

cin>>n>>k;

r=k>3? n*(k-3)-1 : n>1? n-1 : 1;

cout<<r;

return 0;

}

Решение

При каждом разрезе количество кусков бумаги [latex]n[/latex] увеличивается на [latex]1[/latex]. Общее количество вершин [latex]k[/latex] будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на [latex]4[/latex]. При разрезе через две вершины общее количество вершин увеличивается на [latex]2[/latex], а при разрезе через сторону и вершину — на [latex]3[/latex].

При [latex]k>3[/latex] сначала разделим лист на [latex]n[/latex] четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться [latex]n-1[/latex] разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в [latex]k[/latex] — угольник, на что понадобиться [latex]k-4[/latex] разрезов.Выходит, что на получение [latex]n[/latex] [latex]k[/latex]- угольников нужно сделать не меньше [latex]n(k-4)+n-1[/latex] разрезов, значит [latex]r=n(k-3)-1[/latex].

Если же [latex]k=3[/latex], то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на [latex]1[/latex] пока не получим [latex]n[/latex]. В таком случае [latex]r= n-1 [/latex]. Исключение: если [latex]n=1[/latex], то [latex]r=1.[/latex]

Задача: Прямоугольник на плоскости [latex]a \le x \le b, \quad c \le y \le d[/latex] задаётся четырьмя числами (его габаритами): [latex]a, b, c, d.[/latex] Последовательно вводятся габариты [latex]n[/latex] прямоугольников. В процессе ввода находить площадь их пересечения, не запоминая самих габаритов.

NI — «no intersection» — нет общего сегмента

№	[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]S[/latex]	Комментарий
1	-5	-3	1	4	NI	Пройден: нет общего интервала
-2	0	1	4
2	0	4.5	1.2	4.6	NI	Пройден: нет общего интервала
2	4	5	7.4
3	2	5	1	4	NI	Пройден: общая сторона не считается пересечением, т.к. даёт нулевую площадь
5	6	1	4
4	2	4	2	4	4	Пройден
2	4	2	4
5	2	5	1	4	NI	Пройден: не все данные прямоугольники имеют общий сегмент
0	3	2	3
6	7	3	5
6	0	7	0	3	1	Пройден
2	6	1	5
3	5	2	5
4	8	2	3

#include 
#include 
//sort pairs of coordinates by value
void sbv(double &x1, double &x2, double &y1, double &y2)
{
    if( x1 > x2 ) std::swap( x1 , x2 );
    if( y1 > y2 ) std::swap( y1 , y2 );
}
//find whether the rectangles intersect
bool intersect( double b1, double e1, double b2, double e2 )
{
    //"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)
    if( b2 >= e1 || e2 <= b1 ) return false;
    return true;
}

int main()
{
    double a, b, c, d; //meaningful coodinates of rectangle sides
    int n; scanf( "%d", &n );
    scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );
    double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area
    for( int i=1; i<n; i++ )
    {
        scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.
        if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect
        {
            sbv( a, x1, x2, b ); //sort again to find the inner points
            sbv( c, y1, y2, d ); //(image is attached)
            printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );
        }
        else
        {
            printf("System of rectangles has no common area.\n");
            break;
        }

    }
    return 0;
}

#include

//sort pairs of coordinates by value

void sbv(double &x1, double &x2, double &y1, double &y2)

{

if( x1 > x2 ) std::swap( x1 , x2 );

if( y1 > y2 ) std::swap( y1 , y2 );

}

//find whether the rectangles intersect

bool intersect( double b1, double e1, double b2, double e2 )

{

//"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)

if( b2 >= e1 || e2 <= b1 ) return false;

return true;

}

int main()

{

double a, b, c, d; //meaningful coodinates of rectangle sides

int n; scanf( "%d", &n );

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );

double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area

for( int i=1; i<n; i++ )

{

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.

if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect

{

sbv( a, x1, x2, b ); //sort again to find the inner points

sbv( c, y1, y2, d ); //(image is attached)

printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );

}

else

{

printf("System of rectangles has no common area.\n");

break;

}

return 0;

}

Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.

Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.

Протестировать решение можно по ссылке.