Pagini recente » Cod sursa (job #1991391) | Istoria paginii utilizator/veverita927 | Cod sursa (job #962969) | Cod sursa (job #1360445) | Cod sursa (job #1992069)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Punct
{
long double x, y;
};
const int nMax = 120005;
int n;
Punct v[nMax];
int st[nMax], top;
void citire()
{
ifstream in("infasuratoare.in");
in >> n;
for(int i = 1; i <= n; ++i)
in >> v[i].x >> v[i].y;
in.close();
}
inline long double cross_product(const Punct &o, const Punct &p1, const Punct &p2)
{
return (p1.x-o.x) * (p2.y-o.y) - (p1.y-o.y) * (p2.x-o.x);
}
inline bool cmp(const Punct &p1, const Punct &p2)
{
return (cross_product(v[1], p1, p2) < 0);
}
void rezolvare()
{
for(int i = 2; i <= n; ++i)
if(v[i].x < v[1].x)
swap(v[i], v[1]);
sort(v + 2, v + n + 1, cmp);
cout << v[1].x << " " << v[1].y << endl;
st[1] = 1;
st[2] = 2;
top = 2;
for(int i = 3; i <= n; ++i)
{
while(top >= 2 && cross_product(v[st[top-1]], v[st[top]], v[i]) > 0)
--top;
st[++top] = i;
}
}
void afisare()
{
ofstream out("infasuratoare.out");
out << top << "\n";
out << fixed << setprecision(6);
out << v[st[1]].x << " " << v[st[1]].y << "\n"; //FARA ASTA IA 90, NU STIU DE CE
for(int i = top; i >= 2; --i)
out << v[st[i]].x << " " << v[st[i]].y << "\n";
out.close();
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}