Pagini recente » Cod sursa (job #474533) | Cod sursa (job #595980) | Rating Nedelcu Cristian (NedelcuCristian) | Cod sursa (job #763725) | Cod sursa (job #1098176)
#include <algorithm>
#include <fstream>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> pct;
int N, top=2, pmin=1;
pct v[120005], st[120005];
inline double crossprod(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 crossprod(v[1], p1, p2) < 0; }
void convexhull()
{
st[1]=v[1]; st[2]=v[2];
for (int i=3; i<=N; ++i)
{
while ( top>=2 && crossprod(st[top-1], st[top], v[i])>0 )
--top;
st[++top]=v[i];
}
g<<fixed<<setprecision(9)<<top<<'\n';
for (int i=top; i; --i)
g<<st[i].x<<' '<<st[i].y<<'\n';
}
void read()
{
f>>N;
for (int i=1; i<=N; ++i)
{
f>>v[i].x>>v[i].y;
if (v[i]<v[pmin]) pmin=i;
}
swap(v[1], v[pmin]);
sort(v+2, v+N+1, cmp);
}
int main()
{
read();
convexhull();
return 0;
}