Pagini recente » Cod sursa (job #1656824) | Cod sursa (job #1363046)
// infasuratoare
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define pb push_back
#define NMax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
double X[NMax], Y[NMax];
int init = 1;
bool ch[NMax];
vector<int> sol;
void read() {
f>>n;
for (int i=1;i<=n;i++) {
f>>X[i]>>Y[i];
if (X[i] < X[init])
init = i;
}
}
void bl(double &angle) {
if (angle < 0)
angle += 2*M_PI;
}
void solve() {
int cur = init;
double last = 0;
do {
int bst = cur;
double ma = 10000;
sol.pb(cur);
for (int i=1;i<=n;i++) {
if (ch[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;
bst = i;
}
}
last = ma;
cur = bst;
ch[cur] = true;
} while (init != cur);
}
void output() {
reverse(sol.begin(), sol.end());
g<<sol.size()<<'\n';
for (unsigned i=0;i<sol.size();i++)
g<<fixed<<setprecision(12)<<X[sol[i]]<<' '<<Y[sol[i]]<<'\n';
}
int main() {
read();
solve();
output();
f.close(); g.close();
return 0;
}