Pagini recente » Cod sursa (job #3165174) | Cod sursa (job #2345295) | Cod sursa (job #2167432) | Cod sursa (job #3138626) | Cod sursa (job #2446922)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 1e5;
struct point
{
long double x, y;
bool operator < (const point other) const
{
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int N;
point v[NMAX + 5];
vector <point> hull;
long double CrossProd(point O, point A, point B)
{
return (A.y - O.y) * (B.x - O.x) - (B.y - O.y) * (A.x - O.x);
}
inline bool cmp(const point A, const point B)
{
return CrossProd(v[1], A, B) < 0;
}
void ReadAndComputeHull()
{
fin >> N;
int x, y;
for(int i = 1; i <= N; i++)
{
fin >> x >> y;
v[i] = {x, y};
}
for(int i = 2; i <= N; i++)
if(v[i] < v[1])
swap(v[1], v[i]);
sort(v + 2, v + N + 1, cmp);
hull.push_back(v[1]);
for(int i = 2; i <= N; i++)
{
while(hull.size() > 1 && CrossProd(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) > 0)
hull.pop_back();
hull.push_back(v[i]);
}
fout << hull.size() << '\n';
for(auto it : hull)
fout << fixed << setprecision(12) << it.x << ' ' << fixed << setprecision(12) << it.y << '\n';
}
int main()
{
ReadAndComputeHull();
return 0;
}