Pagini recente » Cod sursa (job #2181069) | Cod sursa (job #1472728) | Cod sursa (job #1834068) | Cod sursa (job #2611044) | Cod sursa (job #2866714)
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
struct punct {
double x, y;
};
int n;
vector < int > sol;
punct v[120005];
int Orientare (punct a, punct b, punct c)
{
int aux = (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);
if (aux == 0) return 0; // a, b, c - coliniare
if (aux < 0) return 1; // c - este la stanga segmentului [a,b]
if (aux > 0) return 2; // c - este la dreapta segmentului [a,b]
}
int dist (punct a, punct b)
{
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y); // distanta la patrat dintre 2 puncte
}
void Infasuratoare ()
{
int l = 0;
for (int i=0; i<n; i++) // cautam cel mai din stanga punct care sigur se afla pe infasuratoare
if (v[l].x > v[i].x)
l = i;
int a = l, b, c;
do
{
sol.push_back(a); // adaugam punctul curent la solutie
b = (a + 1) % n; // presupunem ca urmatorul punct e pe infasuratoare
for (int i=0; i<n; i++)
{
if (Orientare(v[a], v[b], v[i]) == 2) // daca gasim un punct la dreapta lui [a,b] actualizam solutia
b = i;
else if (Orientare(v[a], v[b], v[i]) == 0) // daca punctele sunt coliniare il alegem pe cel mai indepartat
{
if (dist(v[a], v[i]) > dist(v[a], v[b]))
b = i;
}
}
a = b; // cel mai bun punct gasit il pregatim pentru iterarea urmatoare
} while (a != l); // repetam pana ajungem de unde am plecat
}
int main()
{
f >> n;
for (int i=0; i<n; i++)
f >> v[i].x >> v[i].y;
Infasuratoare();
g << sol.size() << "\n";
for (int i=0; i<sol.size(); i++)
{
g << fixed << setprecision(6);
g << v[sol[i]].x << " " << v[sol[i]].y << "\n";
}
return 0;
}