Pagini recente » Cod sursa (job #1637432) | Cod sursa (job #2355240) | Cod sursa (job #2397070) | Cod sursa (job #255571) | Cod sursa (job #1362898)
#include <fstream>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define NMax 120005
#define pb push_back
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
vector<int> VECT;
double X[NMax],Y[NMax];
int n,VER[NMax];
void bl(double &angle) {
if (angle < 0)
angle += 2 * M_PI;
}
int main() {
// Citire
f>>n;
for(int i = 1;i <= n; ++i) f>>X[i]>>Y[i];
// Aflarea punctului initial, cel mai de jos din stanga punct
int punct_initial = 1;
for(int i = 1;i <= n; ++i)
if (X[i] < X[punct_initial]) punct_initial = i;
int cur = punct_initial;
double last = 0;
do {
//cout<<last<<endl;
VECT.pb(cur);
double ma = 10000;
int poznoua = cur;
for(int i = 1;i <= n; ++i) {
if (VER[i] || i == cur) continue;
double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);
bl(unghi);
unghi -= last;
bl(unghi);
if (ma > unghi) {
ma = unghi;
poznoua = i;
}
}
last = atan2(X[poznoua]-X[cur],Y[poznoua]-Y[cur]);
bl(last);
cur = poznoua;
VER[cur] = 1;
} while (punct_initial != cur);
reverse(VECT.begin(),VECT.end());
g<<VECT.size()<<'\n';
for(unsigned i = 0;i < VECT.size(); ++i)
g<<fixed<<setprecision(12)<<X[VECT[i]]<<' '<<Y[VECT[i]]<<'\n';
return 0;
}