Pagini recente » Rating Andrei Bunu (andreibunu) | Cod sursa (job #2758235) | Istoria paginii runda/usu4 | Cod sursa (job #1162415) | Cod sursa (job #2415525)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120000;
struct pct
{
long double x, y;
bool operator < (const pct other) const
{
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int N;
pct v[NMAX + 5];
long double CrossProduct(pct A, pct B, pct C)
{
return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) *(C.x - A.x);
}
inline bool cmp(const pct A, const pct B)
{
return CrossProduct(v[1], A, B) > 0;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> v[i].x >> v[i].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);
vector <pct> hull;
hull.push_back(v[1]);
for(int i = 2; i <= N; i++)
{
while(hull.size() > 1 && CrossProduct(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';
return 0;
}