Pagini recente » Cod sursa (job #1803250) | Cod sursa (job #875080) | Cod sursa (job #1362218) | Cod sursa (job #37021) | Cod sursa (job #714482)
Cod sursa(job #714482)
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define NMAX 120010
#define EPS 0.00000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x, y;
int o;
}a[NMAX];
int n, st1[NMAX], st2[NMAX];
void Citeste()
{
int i;
f>>n;
for (i=1; i<=n; ++i) f>>a[i].x>>a[i].y;
}
inline bool cmp(punct A, punct B)
{
if (fabs(A.x-B.x)<EPS)
if (A.y-B.y<EPS) return 1;
else return 0;
else if (A.x-B.x<EPS) return 1;
else return 0;
}
double plan(punct A, punct B, punct C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
void Solve()
{
int i, m=2, x, y, z;
double P;
st1[1]=1; st1[2]=2;
i=3; P=plan(a[st1[m-1]], a[st1[m]], a[i]);
while (P>EPS)
{
++i;
P=plan(a[st1[m]], a[st1[m-1]], a[i]);
}
st1[++m]=i;
for (; i<=n; ++i)
{
if (plan(a[st1[m]], a[st1[m-1]], a[i])>EPS) st1[++m]=i;
else
{
while (plan(a[st1[m]], a[st1[m-1]], a[i])<EPS || fabs(plan(a[st1[m]], a[st1[m-1]], a[i]))==EPS) --m;
st1[++m]=i;
}
}
for (i=1; i<=m; ++i) a[st1[i]].o=i;
x=m;
m=2; st2[1]=n; st2[2]=n-1;
i=n-2; P=plan(a[st2[m-1]], a[st2[m]], a[i]);
while (P<EPS)
{
++i;
P=plan(a[st2[m]], a[st2[m-1]], a[i]);
}
st2[++m]=i;
for (i=n-3; i>0; --i)
if (a[i].o<2)
{
P=plan(a[st2[m]], a[st2[m-1]], a[i]);
if (P>EPS) st2[++m]=i;
else
{
while (plan(a[st2[m]], a[st2[m-1]], a[i])<EPS || fabs(plan(a[st2[m]], a[st2[m-1]], a[i]))==EPS) --m;
st2[++m]=i;
}
}
g<<m+x-2<<"\n";
for (i=x; i>0; --i) g<<fixed<<a[st1[i]].x<<" "<<a[st1[i]].y<<"\n";
for (i=m-1; i>1; --i) g<<fixed<<a[st2[i]].x<<" "<<a[st2[i]].y<<"\n";
}
int main()
{
Citeste();
sort(a+1, a+n+1, cmp);
Solve();
f.close();
g.close();
return 0;
}