Pagini recente » Cod sursa (job #2400378) | Cod sursa (job #498984) | Cod sursa (job #773711) | Cod sursa (job #559481) | Cod sursa (job #1533304)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct point
{
double x, y;
bool operator < (const point &p) const
{
return x<p.x or (x==p.x and y<p.y);
}
};
int n;
vector <point> V, H;
double det (point A, point B, point C)
{
return (double)(B.x-A.x)*(C.y-A.y)-(double)(B.y-A.y)*(C.x-A.x);
}
int main()
{
point p;
in >> n;
for (int i = 0; i < n; ++i)
{ in >> p.x >> p.y;
V.push_back(p);
}
sort(V.begin(), V.end());
H.resize(2*n);
int k = 0;
for (int i = 0; i < n; ++i)
{
while(k >= 2 and det(H[k-2], H[k-1], V[i]) <= 0) --k;
H[k++] = V[i];
}
for (int i = n - 2, t = k + 1; i; --i)
{ while (k >= t and det(H[k-2], H[k-1], V[i]) <= 0) --k;
H[k++] = V[i];
}
H.resize(k);
out << H.size() - 1 << '\n';
for (int i = 0; i < H.size() - 1; ++i) out << fixed << setprecision(6) << H[i].x << ' ' << H[i].y << '\n';
out.close();
return 0;
}