@EvgenySManko

Одно из заданий школьной олимпиады по информатике. Как решить?

Готовлюсь к олимпиаде по информатике, не знаю как решить одно задание:

На координатной плоскости по линиям сетки построено несколько прямоугольников. Необходимо подсчитать число точек с целочисленными координатами, принадлежащими сразу всем этим прямоугольникам.
Составьте программу, которая
• Читает сведения о прямоугольниках из файла tohki.txt;
• Находит и выводит на экран число точек с целочисленными координатами, принадлежащими сразу всем этим прямоугольникам.
Файл tohki.txt, который устроен так:
• В первой строке записано число прямоугольников n (1≤n≤1000);
• Следующая строка содержит сведение о первом прямоугольнике: сначала координаты левой верхней вершины, затем координаты нижней правой вершины прямоугольника – четыре разделенных пробелами целых числа не превосходящих по абсолютной величине 1000;
• В каждой из последующих (n-1) строках сведения о следующем прямоугольнике


Писать буду на Java, вот попытки решения:

import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args)throws Exception{
        FastScanner fs = new FastScanner("tohki.txt");
        try{
            int c = fs.nextInt();
            ArrayList<Integer> list = new ArrayList<Integer>();
            Pramoygolnik[] prm = new Pramoygolnik[c];
            for(int i = 0; i < c; i++){
                prm[i] = new Pramoygolnik(fs.nextInt(), fs.nextInt(), fs.nextInt(), fs.nextInt());
            }
            for(int i = 0; i < c; i++){
                if(i == c-1) break;
                for(int a = 0; a < prm[i].list.size(); a++){
                    if(prm[i].list.contains(prm[i+1].list.get(a))) list.add(Integer.parseInt(prm[i+1].list.get(a)));
                }
            }
            for(int i = 0; i < list.size(); i++){
                for(int a = i + 1; a < list.size(); a++){
                    if(list.get(i)==list.get(a)) list.remove(i);
                }
            }

            System.out.println(list.size());
        }catch (EOFException e){
        }
    }
    static class Pramoygolnik {
        int x1;
        int y1;
        int x2;
        int y2;
        ArrayList<String> list = new ArrayList<String>();
        public Pramoygolnik(int x1, int y1, int x2, int y2){
            this.x1=x1;
            this.y1=y1;
            this.x2=x2;
            this.y2=y2;
            for(int i = y1; i >= y2; i--){
                for(int a = x1; a <= x2; a++){
                    list.add(i+""+a);
                }
            }
        }
    }
    static class FastScanner{
        BufferedReader reader;
        StringTokenizer tokenizer;

        public FastScanner(String name)throws Exception{
            reader = new BufferedReader(new FileReader(name));
        }

        public String tokenizer()throws Exception{
            while(tokenizer==null||!tokenizer.hasMoreTokens()){
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return(tokenizer.nextToken());
        }
        public int nextInt()throws Exception{
            return(Integer.parseInt(tokenizer()));
        }
    }
}


Есть у кого какие идеи?
  • Вопрос задан
  • 1332 просмотра
Решения вопроса 1
leahch
@leahch
3D специалист. Dолго, Dорого, Dерьмово.
О! Самое простое решение, скорее всего самое неэффективное!
Есть двумерный массив поля 1000х1000, заполненный нулями.
Есть Х прямоугольников
Делаем цикл по прямоугольникам
Берем первый и ЗАКРАШИВАЕМ ВСЕ ЕГО ТОЧКИ, делая +=1 в нашем массиве
Берем следующий прямоугольник и повторяем предыдущее

Результат: сканируем все точки нашего массива и выводим те, у которых точка равна Х
Done.
Ну а как это записать на яве, попробуйте сами.

Оптимизировать можно, для этого точки прямоугольников нужно логически складывать (конъюкция, если не ошибаюсь) каждый с последующим, результатом следующего должно быть разультатом сложения. Другими словами, результатом сложения двух прямоугольников является прямоугольник их пересечения. На следующем цикле берем этот результат и следующий прямоугольник, результат используем на следующем.
Можно вообще ничего не рисовать в координатном массиве! Быстро и очень эффективно, всего 4 операции на каждый прямоугольник.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
GavriKos
@GavriKos
Есть идея делить награду за победу в олимпиаде на весь тостер, как вам?
Или идея, что олимпиадные, экзаменационные и прочие домашние задания должен решать не коллективный тостер, а тот кому они заданы.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы