Одне із завдань шкільної олімпіади з інформатики
Готуюся до олімпіади з інформатики, не знаю, як вирішити одне завдання:
На координатній площині лініями сітки побудовано кілька прямокутників. Необхідно підрахувати число точок з цілими координатами, що належать відразу всім цим прямокутникам. Складіть програму, яка • Читає відомості про прямокутники з файлу tohki.txt; • Знаходить і виводить на екран число точок з цілими координатами, що належать відразу всім цим прямокутникам. Файл tohki.txt, який влаштований так: • У першому рядку записано число прямокутників n (1≤n≤1000); • Наступний рядок містить відомості про перший прямокутник: спочатку координати лівої верхньої вершини, потім координати нижньої правої вершини прямокутника – чотири розділені пробілами цілих числа, що не перевищують за абсолютною величиною 1000; • У кожному з наступних (n-1) рядках відомості про наступний прямокутник
Писати буду на Java, ось спроби розв'язання:
Є у кого якісь ідеї?
О! Найпростіше рішення, швидше за все, найнеефективніше! Є двовимірний масив поля 1000х1000, заповнений нулями. Є Х прямокутників Робимо цикл по прямокутниках Беремо перший і ЗАКРАШУЄМО ВСЕ ЙОГО ТОЧКИ, роблячи +=1 у нашому масиві Беремо наступний прямокутник і повторюємо попереднє
Результат: скануємо всі точки нашого масиву та виводимо ті, у яких точка дорівнює Х Done. Ну а як це записати явно, спробуйте самі.
Оптимізувати можна, для цього точки прямокутників потрібно логічно складати (кон'юкція, якщо не помиляюся) кожен з наступним, результатом наступного має бути результатом додавання. Іншими словами, результатом складання двох прямокутниківє прямокутник їхнього перетину. На наступному циклі беремо цей результат та наступний прямокутник, результат використовуємо на наступному. Можна взагалі нічого не малювати в координатному масиві! Швидко та дуже ефективно, всього 4 операції на кожен прямокутник.