Pagini recente » Cod sursa (job #2810777) | Cod sursa (job #2639636) | Cod sursa (job #487055) | Cod sursa (job #703404) | Cod sursa (job #1608826)
#include <cmath>
#include <fstream>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define N 120001
#define INF 1000000001
int n;
double X[N], Y[N];
bool ok[N];
int V[N], nv = 0;
int main()
{
in >> n;
X[0] = INF;
Y[0] = INF;
int punct_initial = 0;
for(int i = 1; i <= n; i++)
{
in >> X[i] >> Y[i];
if(Y[punct_initial] > Y[i])
punct_initial = i;
}
int punct_curent = punct_initial;
bool porneste = 1;
double unghi_anterior = 0;
while(porneste || punct_curent != punct_initial)
{
porneste = 0;
double unghi_optim = -2 * M_PI;
int punct_nou = punct_curent;
V[++nv] = punct_curent;
for(int i = 1; i <= n; i++)
{
if(ok[i] || i == punct_curent)
continue;
double unghi = atan2(Y[i] - Y[punct_curent], X[i] - X[punct_curent]);
if(unghi < 0)
unghi += 2 * M_PI;
unghi -= unghi_anterior;
if(unghi < 0)
unghi += 2 * M_PI;
if(unghi_optim < unghi)
{
unghi_optim = unghi;
punct_nou = i;
}
}
unghi_anterior = atan2(-(Y[punct_nou] - Y[punct_curent]), -(X[punct_nou] - X[punct_curent]));
if(unghi_anterior < 0)
unghi_anterior += 2 * M_PI;
punct_curent = punct_nou;
ok[punct_curent] = 1;
}
out << nv << '\n';
for(int i = nv; i >= 1; i--)
out << X[V[i]] << ' ' << Y[V[i]] << '\n';
return 0;
}