Задача взята с сайта e-olymp
Задача
На белом листе бумаги в клетку нарисовали три закрашенных прямоугольника так, что их стороны лежат на линиях сетки, а вершины имеют известные целые координаты. Найти общее количество закрашенных клеток.
Входные данные
Одно число — количество закрашенных клеток
Выходные данные
В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 0 0 1 1 1 1 2 2 0 0 2 2 |
4 |
| 2 | 2 -2 -2 2 -1 -1 1 1 40 40 41 41 |
17 |
| 3 | -1 2 2 -1 1 0 4 2 1 0 3 6 |
21 |
| 4 | -100 -100 -99 -99 100 100 99 99 -100 -100 100 100 |
40000 |
| 5 | 3 0 4 1 1 0 3 3 1 0 3 3 |
7 |
Решение
Для решения этой задачи создадим структуру «точка» и структуру «прямоугольник». Поскольку для построения прямоугольника достаточно двух точек, структура будет содержать только наименьшую и наибольшую точки прямоугольника. Напишем функции для построения прямоугольника, ввода прямоугольника, вычисления площади прямоугольника, построения пересечения прямоугольников и вычисления площади всех трех прямоугольников. О последних двух стоит написать подробнее.
Для нахождения пересечения прямоугольников рассмотрим проекции координат прямоугольника на координатные оси $x$ и $y$. В случае, если интервалы пересекаются, началом пересечения будет наибольшее из начал интервалов, а концом — наименьшее из их концов. В ином же случае дадим точкам по этой координате одинаковые значения, в результате чего площадь такого прямоугольника и всех пересечений, которые он образует будет равна нулю. Координатами точек пересечения прямоугольников будут, следовательно, соответствующие координаты пересечения интервалов на осях.
После этого задача сводится к написанию функции общей площади. То, что решение, в котором мы просто суммируем площадь трех прямоугольников проходит лишь на один тест, наводит на мысль о том, что мы добавляем площадь пересечений несколько раз. Следовательно, от суммы площадей трех прямоугольников отнимем площадь их пересечения друг с другом и добавим площадь пересечения всех трех(поскольку в случае, если существует пересечение трех, то мы лишний раз отнимаем его площадь).
Записав прямоугольники, в динамический массив, передадим его в функцию нахождения общей площади, и выведем результат.
|
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 <cmath> using namespace std; struct point{int x;int y;}; struct rect{point a;point b;}; rect getrect(point a, point b, rect c){ if(a.x > b.x)swap(a.x,b.x); if(a.y > b.y)swap(a.y,b.y); c.a = a; c.b = b; return c; } rect getrekt(rect c){ point a,b; cin >> a.x >> a.y >> b.x >> b.y; return getrect(a,b,c); } int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);} rect cross(rect l,rect r){ rect cr; point a1,b1; a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x)); a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y)); b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x)); b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y)); return getrect(a1,b1,cr); } int farea(rect *q){ return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2]))); } int main() { rect *q = new rect [3]; for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]); cout<<farea(q); } |
Решение. Многомерные массивы
Для решения с помощью многомерных массивов сдвинем все точки так, чтобы они всегда находились в положительной координатной четверти. Далее, заведем массив, значения которого будут соответствовать квадрату длины 1 координатной плоскости. Далее, заполним единицами все квадраты,содержащиеся в прямоугольника. После этого проходим все значения массива и прибавляем 1 к выводимому значению, если элемент массива равен единице.
|
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 |
#include <iostream> #include <cmath> #define N 100 using namespace std; int main() { int rect[3][4]; int field[2*N][2*N]; int count = 0; for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0; for(int i = 0;i < 3;i++){ for(int k = 0;k < 4;k++){ cin >> rect[i][k]; rect[i][k] = rect[i][k] + N; } } for(int k = 0;k<3;k++){ for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){ for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){ field[i][j]=1; } } } for(int i = 0;i < 2*N;i++){ for(int k = 0;k < 2*N;k++){ if(field[i][k] & 1)count++; } } cout<<count; } |
Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp