Pagini recente » Cod sursa (job #2075101) | Cod sursa (job #950588) | Cod sursa (job #1741134) | Cod sursa (job #1620366) | Cod sursa (job #625580)
Cod sursa(job #625580)
#include<fstream>
#define NMAX 120010
using namespace std;
struct punct
{
double x, y, d;
}a[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=(q.x*w.y)-(q.y*w.x);
if (pla<0 || pla==0 && q.d<w.d) return 0;
return 1;
}
void Solve()
{
int i;
st[1]=1; st[2]=2; st[3]=3;
for (i=4; i<=n; ++i)
{
while (plan(a[st[ns-1]], a[st[ns]], a[i])<0.0) --ns;
if (plan(a[st[ns-1]], a[st[ns]], a[i])!=0.0) st[++ns]=i;
}
g<<ns<<"\n";
for (i=1; i<=ns; ++i)
{
a[st[i]].x-=xx; a[st[i]].y-=yy;
g<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
}
}
int main()
{
Citeste();
Transleaza_Dist();
sort(a+2, a+n+1, cmp);
Solve();
f.close();
g.close();
return 0;
}