Pagini recente » Cod sursa (job #2717431) | Cod sursa (job #2502032) | Cod sursa (job #2659790) | Cod sursa (job #850697) | Cod sursa (job #626050)
Cod sursa(job #626050)
#include<fstream>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define NMAX 120010
using namespace std;
struct punct
{
double x, y, d;
}a[NMAX], b[NMAX], mx;
double xx, yy;
int n, im, st[NMAX], ns=3;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
void Citeste()
{
int i;
punct aux;
f>>n>>a[1].x>>a[1].y;
mx.x=a[1].x; mx.y=a[1].y; im=1;
for (i=2; i<=n; ++i)
{
f>>a[i].x>>a[i].y;
if (a[i].x<mx.x) mx=a[i], im=i;
else if (a[i].x==mx.x && a[i].y<mx.y) mx=a[i], im=i;
}
aux=a[im];
a[im]=a[1];
a[1]=aux;
}
void Transleaza_Dist()
{
int i;
xx=-a[1].x;
yy=-a[1].y;
for (i=1; i<=n; ++i)
a[i].x+=xx, a[i].y+=yy, a[i].d=a[i].x*a[i].x+a[i].y*a[i].y;
}
inline 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;
}
int cmp(punct q, punct w)
{
double pla=plan(a[1], q, w);
if (pla<0 || (pla==0 && q.d<w.d)) return 0;
return 1;
}
void Solve()
{
int i, m=2;
b[1]=a[1]; b[2]=a[2];
for (i=3;i<=n;++i)
if (plan(a[1],a[i-1],a[i])>0) b[++m]=a[i];
st[1]=1; st[2]=2; st[3]=3;
for (i=4; i<=m; ++i)
{
while (plan(b[st[ns-1]], b[st[ns]], b[i])<0.0) --ns;
st[++ns]=i;
}
g<<ns<<"\n";
for (i=1; i<=ns; ++i)
{
b[st[i]].x-=xx; b[st[i]].y-=yy;
g<<fixed<<b[st[i]].x<<" "<<b[st[i]].y<<"\n";
}
}
int main()
{
Citeste();
Transleaza_Dist();
sort(a+2, a+n+1, cmp);
Solve();
f.close();
g.close();
return 0;
}