Pagini recente » Cod sursa (job #2009373) | Cod sursa (job #1720376) | Cod sursa (job #708043) | Cod sursa (job #2058435) | Cod sursa (job #1284140)
#include <fstream>
#include <vector>
using namespace std;
const char INPUT_FILE_NAME[] = "infasuratoare.in";
const char OUTPUT_FILE_NAME[] = "infasuratoare.out";
struct Punct{
double x;
double y;
};
vector<Punct> *incarcaSetPuncte(const char filename[]){
ifstream fin(filename);
int n;
fin >> n;
vector<Punct> *set_puncte = new vector<Punct>(n);
for(int i = 0; i < (*set_puncte).size(); ++i){
fin >> (*set_puncte)[i].x >> (*set_puncte)[i].y;
}
fin.close();
return set_puncte;
}
const int STANGA = -1;
const int DREAPTA = 1;
const int COLINIAR = 0;
int orientareUnghiulara(const Punct &a, const Punct &b, const Punct &c){
double rezultat = (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
if(rezultat < 0){
return STANGA;
}else if(rezultat > 0){
return DREAPTA;
}
return COLINIAR;
}
void interschimba(vector<Punct> *set_puncte, int i, int j){
Punct temp = (*set_puncte)[i];
(*set_puncte)[i] = (*set_puncte)[j];
(*set_puncte)[j] = temp;
}
void plaseazaPunctPornire(vector<Punct> *set_puncte){
Punct stanga_jos = (*set_puncte)[0];
int k = 0;
for(int i = 1; i < (*set_puncte).size(); ++i){
if((*set_puncte)[i].x < stanga_jos.x){
stanga_jos = (*set_puncte)[i];
k = i;
}else if((*set_puncte)[i].x == stanga_jos.x){
if((*set_puncte)[i].y < stanga_jos.y){
stanga_jos = (*set_puncte)[i];
k = i;
}
}
}
interschimba(set_puncte, 0, k);
}
int partitieQuickSort(vector<Punct> *set_puncte, int start, int end){
Punct pivot = (*set_puncte)[start];
int i = start + 1;
int j = end;
while(true){
while(orientareUnghiulara((*set_puncte)[0], pivot, (*set_puncte)[i]) == DREAPTA){
if(i == end){
break;
}
++i;
}
while(orientareUnghiulara((*set_puncte)[0], pivot, (*set_puncte)[j]) == STANGA){
--j;
}
if(i >= j){
break;
}
interschimba(set_puncte, i, j);
}
//interschimba pivotul de pe pozitia start, cu elementul [j]
interschimba(set_puncte, start, j);
return j;
}
void quickSortPuncte(vector<Punct> *set_puncte, int start, int end){
if(start >= end){
return;
}
int index_pivot = partitieQuickSort(set_puncte, start, end);
quickSortPuncte(set_puncte, start, index_pivot - 1);
quickSortPuncte(set_puncte, index_pivot + 1, end);
}
void sorteazaPuncte(vector<Punct> *set_puncte){
quickSortPuncte(set_puncte, 1, (*set_puncte).size() - 1);
}
int infasoaraConvex(vector<Punct> *set_puncte){
plaseazaPunctPornire(set_puncte);
sorteazaPuncte(set_puncte);
int nr_varfuri_convex = 1; //nr varfuri gasite, inafara de punctPornire
for(int i = 2; i < (*set_puncte).size(); ++i){
Punct a = (*set_puncte)[nr_varfuri_convex-1];
Punct b = (*set_puncte)[nr_varfuri_convex];
Punct c = (*set_puncte)[i];
while(orientareUnghiulara(a, b, c) == DREAPTA){
if(nr_varfuri_convex > 1){
--nr_varfuri_convex;
a = (*set_puncte)[nr_varfuri_convex-1];
b = (*set_puncte)[nr_varfuri_convex];
}else{
c = (*set_puncte)[++i];
}
}
interschimba(set_puncte, ++nr_varfuri_convex, i);
}
return (nr_varfuri_convex + 1);
}
void scriePoligonConvex(const char filename[], vector<Punct> *set_puncte, int nr_varfuri){
//Scrie rezultatul in fisier
ofstream fout(filename);
fout << nr_varfuri << "\n";
for(int i = 0; i < nr_varfuri; ++i){
fout << (*set_puncte)[i].x << " " << (*set_puncte)[i].y << "\n";
}
fout.close();
}
int main(int argc, char *argv[]){
vector<Punct> *set_puncte;
set_puncte = incarcaSetPuncte(INPUT_FILE_NAME);
int nr_varfuri = infasoaraConvex(set_puncte);
scriePoligonConvex(OUTPUT_FILE_NAME, set_puncte, nr_varfuri);
delete set_puncte;
return 0;
}