Готовлюсь к олимпиаде по информатике, не знаю как решить одно задание:
На координатной плоскости по линиям сетки построено несколько прямоугольников. Необходимо подсчитать число точек с целочисленными координатами, принадлежащими сразу всем этим прямоугольникам.
Составьте программу, которая
• Читает сведения о прямоугольниках из файла 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()));
}
}
}
Есть у кого какие идеи?
Простой
