Pagini recente » Cod sursa (job #999318) | Cod sursa (job #1373235) | Cod sursa (job #1539101) | Profil M@2Te4i | Cod sursa (job #1113076)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N, top=2, pmin=1;
struct pct{ double x, y; }v[120002], st[120002], aux;
double cprod(const pct &A, const pct &B, const pct &C)
{ return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); }
inline int cmp(const pct& p1, const pct& p2) { return cprod(v[1], p1, p2) < 0; }
void ConexHull()
{
st[1]=v[1]; st[2]=v[2];
for (int i=3; i<=N; ++i)
{
while (top>1 && cprod(st[top-1], st[top], v[i])>0)
--top;
st[++top]=v[i];
}
}
int main()
{
f>>N;
for (int i=1; i<=N; ++i)
{
f>>v[i].x>>v[i].y;
if (v[pmin].x>v[i].x || (v[pmin].x==v[i].x && v[pmin].y>v[i].y)) pmin=i;
}
swap(v[1], v[pmin]);
sort(v+2, v+N+1, cmp);
ConexHull();
g<<fixed<<setprecision(6)<<top<<'\n';
for (int i=1; i<=top; ++i)
g<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}