Pagini recente » Cod sursa (job #2732794) | Cod sursa (job #2319629) | Cod sursa (job #637300) | Cod sursa (job #709295) | Cod sursa (job #2579707)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const long double eps = 1e-12;
struct Punct
{
long double x, y;
Punct(long double abscisa, long double ordonata) : x(abscisa), y(ordonata) {}
Punct() {}
// se vor compara puncte, deci trebuie sa
// supraincarcam operatorii de egalitate
bool operator ==(const Punct& other)
{
return (abs(x - other.x) < eps) && (abs(y - other.y) < eps);
}
bool operator !=(const Punct& other)
{
return (abs(x - other.x) > eps) || (abs(y - other.y)> eps);
}
};
Punct g;
int Orientare(const Punct& A, const Punct& B, const Punct& C)
{
long double temp = (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
if (temp < 0)
return -1;
else if (temp < eps)
return 0;
else
return 1;
}
void Citire(vector<Punct>& P, int& N)
{
cin >> N;
long double x, y;
for (int i = 1; i <= N; ++i)
{
cin >> x >> y;
P.push_back(Punct(x, y));
}
}
vector<Punct> Jarvis(const vector<Punct>& P)
{
int start = 0; // vectorii incep de la 0
for (int i = 1; i < P.size(); ++i)
if (P[i].x < P[start].x || (P[i].x == P[start].x && P[i].y > P[start].y))
start = i;
vector<Punct> CH;
CH.push_back(P[start]);
for (int i = 0; i < CH.size(); ++i)
{
Punct nextPct = (CH[i] == P[0]) ? P[1] : P[0];
for (int j = 0; j < P.size(); ++j)
if (Orientare(CH[i], P[j], nextPct) > 0)
nextPct = P[j];
if (nextPct != CH[0])
CH.push_back(nextPct);
}
return CH;
}
inline bool cmp(Punct a, Punct b)
{
return atan2(a.y - g.y, a.x - g.x) > atan2(b.y - g.y, b.x - g.x);
}
int main()
{
int N;
vector<Punct> P;
Citire(P, N);
vector<Punct> CH = Jarvis(P);
cout << CH.size() << endl;
for (size_t i = 0; i < CH.size(); ++i)
{
g.x += CH[i].x;
g.y += CH[i].y;
}
g.x /= CH.size();
g.y /= CH.size();
sort(CH.begin(), CH.end(), cmp);
for (size_t i = 0; i < CH.size(); ++i)
cout << fixed << setprecision(6) << CH[i].x << " " << CH[i].y << "\n";
return 0;
}