Pagini recente » Cod sursa (job #1881834) | Cod sursa (job #2806949) | Cod sursa (job #2458505) | Cod sursa (job #521257) | Cod sursa (job #1485667)
#include <iostream>
#include <fstream>
#include <list>
#include <iomanip>
#include <cmath>
#include <cstdio>
using namespace std;
struct elem
{
double x, y;
};
int main()
{
list <elem> rez;
bool *use;
ifstream input("infasuratoare.in");
int n;
input >> n;
double **a = (double **)new double[n];
use = new bool[n];
for (int i = 0; i < n; i++)
{
a[i] = (double*)new double[2];
input >> a[i][0];
input >> a[i][1];
use[i] = false;
}
input.close();
int min = 0, start = 0, k = 0;
for (int i = 1; i < n; i++)
if (a[i, 1] < a[min, 1])
min = i;
else if (a[i, 1] == a[min, 1] && a[i, 0] < a[min, 0])
min = i;
start = min;
use[start] = true;
elem *e = new elem();
e->x = a[min][0];
e->y = a[min][1];
rez.push_back(*e);
double p1 = a[min][0] - 10, p2 = a[min][1];
double cosin = 1;
bool ok = true;
while (true)
{
ok = false;
cosin = 1;
for (int i = 0; i < n; i++)
{
double bc = sqrt(pow((p1 - a[min][0]), 2) + pow(p2 - a[min][1], 2));
double ab = sqrt(pow(a[min][0] - a[i][0], 2) + pow(a[min][1] - a[i][1], 2));
double ac = sqrt(pow(a[i][0] - p1, 2) + pow(a[i][1] - p2, 2));
double cos = (pow(ab, 2) + pow(bc, 2) - pow(ac, 2)) / (2 * ab * bc);
if (cosin > cos)
{
cosin = cos;
k = i;
ok = true;
}
}
if (use[k])
{
break;
}
if (ok)
{
e = new elem();
e->x = a[k][0];
e->y = a[k][1];
rez.push_back(*e);
use[k] = true;
p1 = a[min][0];
p2 = a[min][1];
min = k;
}
else
break;
}
ofstream output("infasuratoare.out");
output << rez.size() <<endl;
for (list<elem>::iterator it = rez.begin(); it != rez.end(); ++it)
output << setprecision(6) << it->x << " " << it->y << endl;
output.close();
return 0;
}