REŠENJE PRIMERA "TRANSLACIJA TAČAKA"

Dobrodošli na stranicu posvećenu rešavanju problema "Translacija tačaka". Ovaj zadatak predstavlja zanimljiv spoj geometrije i programiranja, omogućavajući vam da praktično primenite osnovne matematičke operacije i algoritamsko razmišljanje. Cilj je translacija niza tačaka u ravni tako da im težište postane u koordinatnom početku, što je čest korak u analizi podataka i računskoj geometriji.
Na ovoj stranici naći ćete:

• Detaljno objašnjenje zadatka i postupka rešavanja.
• Praktične primere ulaza i izlaza koji ilustruju specifične slučajeve.
• Analizu efikasnosti algoritma i korisne savete za implementaciju.

Bilo da ste početnik ili napredni programer, cilj je da vam ovo uputstvo pomogne da bolje razumete koncept težišta i njegovo prilagođavanje u kontekstu programskih zadataka.

Tekst:

/*
Date su koordinate  N tačaka u ravni. Translirati tačke tako da im težište bude u koordinatnom početku.

Ulaz
U prvoj liniji standardnog ulaza nalazi se prirodan broj n (1≤n≤100). U sledećih n
 linija nalaze se po dva realna broja, koji predstavljaju x i y koordinate tačaka.

Izlaz
Na standardnom izlazu prikazati koordinate tačaka posle translacije, za svaku tačku u jednoj liniji njenu
x pa y koordinatu, koordinate odvojiti jednom prazninom i prikazati ih na dve decimale.

Primer
Ulaz
3
0 0
1 0
2 3
Izlaz
-1.00 -1.00
0.00 -1.00
1.00 2.00
*/Kompletan ulazni/izlazni primer:Dodavanje više ulaznih primera omogućava korisnicima da bolje razumeju kako algoritam funkcioniše u različitim scenarijima. Na primer:

1. Jedna tačka:

Ulaz1  
3.0 4.0
​Izlaz​0.00 0.00
2. Tačke na pravoj liniji:Ulaz
​3  
0.0 0.0  
1.0 1.0  
2.0 2.0
Izlaz
​-1.00 -1.00  
0.00 0.00  
1.00 1.00

3. Simetrične tačke u ravni:Ulaz
4  
-1.0 -1.0  
1.0 1.0  
-1.0 1.0  
1.0 -1.0
Izlaz
-1.00 -1.00  
1.00 1.00  
-1.00 1.00  
1.00 -1.00

---

Rešenje u programskom jeziku C

#include <stdio.h>

int main() {
int n; // Broj tačaka
    scanf("%d", &n); // Učitavanje broja tačaka

double x[100], y[100]; // Nizovi za čuvanje x i y koordinata tačaka
for (int i = 0; i < n; i++) {
scanf("%lf %lf", &x[i], &y[i]); // Učitavanje koordinata svake tačke
    }

double Tx, Ty;      // Koordinate težišta (centar mase)
    double zbX = 0, zbY = 0; // Promenljive za sumu x i y koordinata

// Izračunavanje suma x i y koordinata
for (int i = 0; i < n; i++) {
        zbX += x[i];
        zbY += y[i];
    }

// Računanje koordinata težišta
    Tx = zbX / n; 
    Ty = zbY / n;

// Translacija tačaka
for (int i = 0; i < n; i++) {
        printf("%.2f %.2f\n", x[i] - Tx, y[i] - Ty); // Ispis novih koordinata sa dve decimale
    }

return 0; // Kraj programa
}

Detaljno objašnjenje koda:

1. Deklaracija i unos broja tačaka:
   • int n; scanf("%d", &n);
     Ovaj deo koda unosi broj tačaka nnn, gde je 1≤n≤100.
2. Čuvanje koordinata tačaka:
   • Koriste se dva niza (x i y) za čuvanje x i y koordinata svih tačaka.
3. Izračunavanje suma x i y koordinata:
   • zbX i zbY inicijalno su postavljeni na 0.
   • U petlji for (int i = 0; i < n; i++), svaka koordinata se dodaje na odgovarajuću sumu.
4. Računanje težišta:
   • Težište (Tx, Ty) se izračunava kao prosečna vrednost svih x i y koordinata: Tx=suma svih x koordinatan,Ty=suma svih y koordinata​
5. Translacija tačaka:
   • Svaka tačka se pomera tako da je udaljena od svog originalnog položaja za vektor težišta.
   • Nove koordinate tačke iii se dobijaju kao: xnova=xstara−Tx,ynova=ystara−Ty
6. Ispis rezultata:
   • Koordinate nakon translacije ispisuju se na dve decimale pomoću printf("%.2f %.2f\n", ...).

---

Objašnjenje zadatka

Ovaj program je napisan u C++ i služi za translaciju tačaka u ravni tako da im težište postane u koordinatnom početku. Evo kako program funkcioniše:

1. Unos Broja Tačaka:
   
   • Prvo, program učitava broj tačaka n koje će se obraditi.
2. Unos Koordinata:
   
   • U sledećem koraku, program koristi nizove x i y za čuvanje x i y koordinata tačaka. Učitava koordinate svake tačke iz standardnog ulaza.
3. Izračunavanje Težišta:
   
   • Program koristi promenljive zbX i zbY za sumiranje x i y koordinata svih tačaka. Težište (centar) se računa kao prosečna vrednost koordinata svih tačaka, tj. Tx i Ty su prosečne x i y koordinate.
4. Translacija Tačaka:
   
   • Nakon što je izračunato težište, svaka tačka se translira tako što se od njenih originalnih koordinata oduzmu koordinate težišta (Tx i Ty). Rezultat se prikazuje sa dve decimale.
5. Ispis Rezultata:
   
   • Na kraju, program koristi printf za formatiranje i ispis koordinata svake tačke nakon translacije, sa dve decimale.

Zašto ovo rešenje funkcioniše?

Težište skupa tačaka u ravni definiše se kao prosečna vrednost njihovih koordinata. Translacijom svih tačaka za negativne vrednosti koordinata težišta (Tx,Ty), težište se pomera u koordinatni početak (0,0).
Komentar:Kod je optimizovan za O(n) složenost, što znači da se svaka tačka obrađuje jednom u dve glavne petlje. Ovo rešenje je efikasno za zadate uslove n≤100.

Rešenje u C++

#include <iostream>
#include <vector>
#include <iomanip>
using namespacestd;

int main() {
int n;
cin >> n;

vector<double> x(n), y(n);
double zbX = 0, zbY = 0;

// Unos koordinata i sumiranje
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        zbX += x[i];
        zbY += y[i];
    }

// Računanje težišta
double Tx = zbX / n, Ty = zbY / n;

// Translacija tačaka i ispis rezultata
for (int i = 0; i < n; i++) {
cout << fixed << setprecision(2) << (x[i] - Tx) << " " << (y[i] - Ty) << endl;
    }

return 0;
}Objašnjenje zadatka:

1. Unos podataka:
   • Program učitava broj tačaka nnn, a zatim njihove koordinate (x,yx, yx,y) i čuva ih u strukturama podataka.
2. Računanje težišta:
   • Težište je centar mase svih tačaka, računa se kao prosečna vrednost xxx-koordinata i yyy-koordinata: Tx=∑x/n,Ty=∑y/n​
3. Translacija:
   • Svaka tačka se pomera tako da težište postane u koordinatnom početku. Translacija se vrši oduzimanjem koordinata težišta od koordinata svake tačke: x′=x−Tx,y′=y−Ty​
4. Formatiran izlaz:
   • Koristi se formatiranje na dve decimale da bi izlaz bio jasan i precizan.

Efikasnost:Važno je naglasiti efikasnost algoritma. U ovom slučaju:

1. Složenost:
   Algoritam ima vremensku složenost O(n), jer:
   
   • Prva petlja prolazi kroz sve tačke da bi sabrala njihove koordinate (O(n)).
   • Druga petlja prolazi kroz sve tačke radi translacije (O(n)).
   • Konstantne operacije unutar petlji ne utiču značajno na složenost.
2. Prostor:
   
   • Koristi O(n) memorije za skladištenje koordinata x i y, što je optimalno za zadate uslove n≤100.
3. Praktična ograničenja:
   
   • Čak i za najveći dozvoljeni unos (n=100), algoritam je brz i efikasan, jer se radi o linearnom skeniranju koordinata.

Napomena: Ovaj nivo efikasnosti je primer optimalnog dizajna za probleme sa malim brojem unosa, dok bi za veće podatke (npr. n≫1000) bilo poželjno istražiti optimizacije za paralelno računanje ili prostorno efikasnije metode.

---

Povratak: Nizovi-primeri

---