Pagini recente » Cod sursa (job #68201) | Cod sursa (job #1492116) | Cod sursa (job #1910857) | Cod sursa (job #2874093) | Cod sursa (job #295023)
Cod sursa(job #295023)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <math.h>
#define dim 120100
using namespace std;
vector<int> v;
int n, fol[dim], in;
double x[dim], y[dim];
int main()
{
int i, cur, move, pozn;
double last, unghi, ma;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d\n", &n);
x[0]=10e11;
y[0]=10e11;
in=0;
for (i=1; i<=n; i++)
{
scanf("%lf %lf\n", &x[i], &y[i]);
if (x[i]<x[in] || (x[i]==x[in] && y[i]<y[in])) in=i;
}
move=1;
cur=in;
last=0;
while (move || cur!=in)
{
move=0;
v.push_back(cur);
pozn=cur;
ma=10000;
for (i=1; i<=n; i++)
{
if (fol[i] || i==cur) continue;
unghi=atan2(x[i]-x[cur], y[i]-y[cur]);
if (unghi<0) unghi+=2*M_PI;
unghi-=last;
if (unghi<0) unghi+=2*M_PI;
if (ma>unghi)
{
ma=unghi;
pozn=i;
}
}
last=atan2(x[pozn]-x[cur], y[pozn]-y[cur]);
if (last<0) last+=2*M_PI;
cur=pozn;
fol[cur]=1;
}
reverse(v.begin(), v.end());
printf("%d\n", v.size());
for (i=0; i<v.size(); i++) printf("%lf %lf\n", x[v[i]], y[v[i]]);
return 0;
}