Pagini recente » Cod sursa (job #1666295) | Cod sursa (job #1841440) | Cod sursa (job #1284459) | Cod sursa (job #530130) | Cod sursa (job #2722668)
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
point()
{
x = 0;
y = 0;
}
point(double X, double Y)
{
x = X;
y = Y;
}
};
const double PI = atan(1) * 4;
int n;
bool used[120001];
point p[120001];
int main()
{
f >> n;
for (int i=1; i<=n; i++)
f >> p[i].x >> p[i].y;
int first = 1;
for (int i=1; i<=n; i++)
if (p[i].x < p[first].x)
first = i;
bool m = true;
int cur = first;
double last = 0;
vector < int > ans;
while (m || cur != first)
{
m = false;
ans.push_back(cur);
double ma = 10000;
int pos = 0;
for (int i=1; i<=n; i++)
if (!used[i] && i != cur)
{
double unghi = atan2(p[i].x - p[cur].x, p[i].y - p[cur].y);
if (unghi < 0)
unghi += 2.0 * PI;
unghi -= last;
if (unghi < 0)
unghi += 2.0 * PI;
if (unghi < ma)
{
ma = unghi;
pos = i;
}
}
last = atan2(p[pos].x - p[cur].x, p[pos].y - p[cur].y);
if (last < 0)
last += 2 * PI;
cur = pos;
used[cur] = true;
}
g << ans.size() << "\n";
for (int i=ans.size()-1; i>=0; i--)
g << fixed << setprecision(6) << p[ans[i]].x << " " << p[ans[i]].y << "\n";
return 0;
}