Pagini recente » Cod sursa (job #485867) | Cod sursa (job #1090884) | Cod sursa (job #2829628) | Cod sursa (job #491338) | Cod sursa (job #2866650)
#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; // 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]
}
void Infasuratoare ()
{
int l = 0;
for (int i=0; i<n; i++)
if (v[l].x > v[i].x)
l = i;
int a = l, b, c;
do
{
sol.push_back(a);
b = (a + 1) % n;
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;
}
a = b;
} while (a != l);
}
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=1; i<sol.size(); i++)
{
g << fixed << setprecision(6);
g << v[sol[i]].x << " " << v[sol[i]].y << "\n";
}
g << fixed << setprecision(6);
g << v[sol[0]].x << " " << v[sol[0]].y << "\n";
return 0;
}