Pagini recente » Cod sursa (job #706217) | Cod sursa (job #793795) | Cod sursa (job #1984981) | Cod sursa (job #1402796) | Cod sursa (job #1485711)
#include <iostream>
#include <fstream>
#include <list>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
struct elem
{
double x, y;
};
vector<elem> v;
int main()
{
list <elem> rez;
ifstream input("infasuratoare.in");
int n;
input >> n;
elem *e;
for (int i = 0; i < n; i++)
{
e = new elem();
input >> e->x;
input >> e->y;
v.push_back(*e);
}
elem elemMin;
input.close();
cout << n << endl;
cout << v.size();
int min = 0, start = 0, k = 0;
for (int i = 1; i < v.size();i++)
if (v[i].y < v[min].y)
min = i;
else
if (v[i].y == v[min].y && v[i].x < v[min].x)
min = i;
start = min;
rez.push_back(v[min]);
elemMin = v[min];
double p1 = v[min].x - 10, p2 = v[min].y;
double cosin = 1;
bool ok = true;
while (true)
{
ok = false;
cosin = 1;
for (int i = 0; i < v.size(); i++)
{
double bc = sqrt(pow((p1 - elemMin.x), 2) + pow(p2 - elemMin.y, 2));
double ab = sqrt(pow(elemMin.x - v[i].x, 2) + pow(elemMin.y - v[i].y, 2));
double ac = sqrt(pow(v[i].x - p1, 2) + pow(v[i].y - 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 (k == start)
{
break;
}
if (ok)
{
rez.push_back(v[k]);
p1 = elemMin.x;
p2 = elemMin.y;
elemMin = v[k];
v.erase(v.begin() + k);
}
else
break;
}
ofstream output("infasuratoare.out");
output << rez.size() <<endl;
for (list<elem>::iterator it = rez.begin(); it != rez.end(); ++it)
output << setprecision(9) << fixed << it->x << " " << it->y << endl;
output.close();
return 0;
}