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:
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.
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
*/
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:
- Jedna tačka:
1
3.0 4.0
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
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
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
}
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:
- Deklaracija i unos broja tačaka:
- int n; scanf("%d", &n);
Ovaj deo koda unosi broj tačaka nnn, gde je 1≤n≤100.
- int n; scanf("%d", &n);
- Čuvanje koordinata tačaka:
- Koriste se dva niza (x i y) za čuvanje x i y koordinata svih tačaka.
- 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.
- 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
- 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
- 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:
- Unos Broja Tačaka:
- Prvo, program učitava broj tačaka n koje će se obraditi.
- 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.
- 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.
- 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.
- 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 namespace std;
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;
}
#include <vector>
#include <iomanip>
using namespace std;
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:
- Unos podataka:
- Program učitava broj tačaka nnn, a zatim njihove koordinate (x,yx, yx,y) i čuva ih u strukturama podataka.
- 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
- 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
- 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:
- 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.
- Prostor:
- Koristi O(n) memorije za skladištenje koordinata x i y, što je optimalno za zadate uslove n≤100.
- 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.
Povratak: Nizovi-primeri