C# - Kvadrati

C# - Kvadrati

Avtor: Petra Adamič

Opis problema in ideja rešitve

Opis problema


Podane so celoštevilske koordinate n točk, ki ležijo v ravnini. Vsak par teh točk določa pravokotnik, ki ima s koordinatnima osema vzporedne stranice in ena točka leži v njegovem spodnjem levem oglišču, druga pa v zgornjem desnem oglišču. Napiši program, ki učinkovito poišče število takih pravokotnikov, ki so kvadrati. Štej tudi izrojene kvadrate, pri katerih spodnje levo in zgornje desno oglišče sovpadata. Število točk n je največ 100. Območje, na katerem ležijo točke v ravnini, je znotraj kvadrata: -10 000 ≤ x ≤ 10 000, -10 000 ≤ y 10 000.

Koordinate točk bodo podane na datoteki, kjer bo vsaka točka v svoji vrstici, koordinati pa ločeni s presledkom.



Ideja rešitve


Glavna ideja programa je, da pregledamo vse pare točk med sabo in preverimo, če imamo kvadrat. Preverimo tako, da pogledamo, če je razdalja med x koordinatama točk enaka razdalji med y koordinatama točk.

Razlaga algoritma

Najprej preberemo koordinate točk iz datoteke, ki jih shranimo v seznam podseznamov, kjer vsak podseznam predstavlja eno točko. Nato z dvema zankama for pregledamo vse možne pare točk in vsakič pogledamo, če nek par točk tvori kvadrat. To ugotovimo tako, da primerjamo razdalji med x koordinatama in y koordinatama teh dveh točk. Če je razdalja enaka, imamo kvadrat.


static void Main(string[] args)
        {
            //podatki bodo na datoteki, vsaka točka v svoji vrstici, koordinati ločeni s presledkom
            Console.Write("Vnesi ime datoteke: ");
            string imeDatoteke=Console.ReadLine();
            int stevec = 0;//štejemo kvadrate
            List<int> podseznam;
            List<List<int>> seznam=new List<List<int>>();//seznam seznamov
            string vrstica;
            using (StreamReader beri = new StreamReader(imeDatoteke))
            {
               while ((vrstica = beri.ReadLine()) != null)
                {
                    podseznam = new List<int>();//vsakič ga nastavimo na prazen
                    string[] tab = vrstica.Split();
                    int x = int.Parse(tab[0]);//dobimo x koordinato točke
                    int y = int.Parse(tab[1]);//dobimo y koordinato točke
                    podseznam.Add(x);
                    podseznam.Add(y);
                    seznam.Add(podseznam);//dobimo seznam seznamov, ki predstavljajo točke
                }
            }
            int i = 0;
            while (i < seznam.Count - 1)//gremo po točkah do predzadnje
            {
                int j = i + 1;
                while (j < seznam.Count)//gremo po točkah od točke, ki jo določa i do zadnje točke
                {
                    //če je razdalja med istoležnima koordinatama enaka, pomeni da imamo kvadrat
                    if((seznam[i][0] - seznam[j][0])==(seznam[i][1]-seznam[j][1]))
                    {
                        stevec++;
                    }
                    j++;
                }
                i++;
            }
            //izpišemo število kvadratov
            Console.Write("Število kvadratov je: " + stevec);
            Console.ReadKey();
        }

Testni primeri

Vzamemo tekstovno datoteko, kjer imamo v vsaki vrstici napisane koordinate točk. Na datoteki imamo naključna števila v dovoljenem rangu.

Naredila sem 4 različne datoteke s koordinatami. Ena datoteka je prazna.

(kvadrati-izpis.PNG)
primer izpisa 1


(kvadrati-izpis1.PNG)
primer izpisa 2


(kvadrati-izpis2.PNG)
primer izpisa 3


(kvadrati-izpis3.PNG)
primer izpisa 4

Filmček

0%
0%