Pagini recente » Cod sursa (job #2702770) | Cod sursa (job #1262616) | Cod sursa (job #2252814) | Cod sursa (job #724998) | Cod sursa (job #2892474)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, nr_puncte_infasuratoare_convexa;
int indice_minim;
pair<double, double>punct_minim;
vector<pair<double, double>>puncte;
vector<pair<double, double>>varfuri_acoperire;
double determinant(pair<double, double>p, pair<double, double> q, pair<double, double>r){
return (q.second - p.second) * (r.first - q.first) - (q.first - p.first) * (r.second - q.second);
}
void acoperire_convexa(){
int p = indice_minim;
int q;
do{
varfuri_acoperire.push_back(puncte[p]);
q = (p + 1) % n;
for(int i = 0; i < n; i++){
if(determinant(puncte[p], puncte[i], puncte[q]) < 0)
q = i;
}
p = q;
}while(p != indice_minim);
g << varfuri_acoperire.size() << "\n";
for(int i = 0; i < varfuri_acoperire.size(); i++)
g << fixed << setprecision(6) << varfuri_acoperire[i].first << " " << varfuri_acoperire[i].second << "\n";
}
int main(){
f >> n;
puncte.resize(n);
for(int i = 0; i < n; i++){
f >> puncte[i].first >> puncte[i].second;
if(i == 0)
punct_minim = puncte[i];
else if (punct_minim.first > puncte[i].first){
punct_minim = puncte[i];
indice_minim = i;
}
}
acoperire_convexa();
return 0;
}