Page 3 of 3

### Double type rounding

Posted: Tue Sep 05, 2006 5:35 pm
Hi guys,

I am writing some code to do normal rounding passing it in the value say 0.085 rounding it to .01 places where i should get 0.09. (note this only one example I may want to round it .001, etc )
Has anyone out there a neat way I could so this in c++.

nano72

Posted: Tue Sep 05, 2006 6:25 pm
If d is the number of digits you want to round to, do this:

Code: Select all

``````double x = 0.085;
double m = pow( 10.0, d );
x = (int)(x * m + 0.5) / m;
``````
Note the doubles. Make sure you're not dividing integers by integers.

Posted: Tue Sep 05, 2006 7:09 pm
Thanks for that but checked it out and it doesn't do alot
My return value is 0.000000
where i would expect 0.09

the substituding is

double x = 0.085;
double m = pow( 10.0, 0.01);
x = (int)(0.085 * m + 0.5) / m;

Any ideas ..

Posted: Tue Sep 05, 2006 8:38 pm
change 0.01 to 2.

Posted: Wed Sep 06, 2006 11:13 am
Hi Abednego,
Tried that substitude and it works for the .085 combination I now get .09 which is correct!
BUT for the .086 - i get .091 expect .09
for .081 - i get .86 expect .08
.08 get .085 where i expect to get .08 if rounding to nearest 0.01

Any ideas here ..

Thanks again !

Posted: Fri Sep 22, 2006 10:50 pm
please, some help, this is the first time i write this type of binary search, can any one find the bug

Code: Select all

``````
if(m != k && n != 0)
{
while(fabs(start-end) > EPS)
{
middle = (start+end)/2;

/* Build Bipartite graph using matching condition d<=middle */
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
cap[i][j] = 0;
}

for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
d = hypot(xg[i]-xh[j], yg[i]-yh[j]);

if(d <= middle)	cap[i][j] = 1;
}
}

n_right_side = m;	n_left_side = n;

max = Bipartite();

if(max >= m-k)		end   = middle;
else				start = middle;
}
}

cout<<"Case #"<<l<<":\n";

if(m == k)
cout<<0<<"\n";
else if(n == 0)
else
cout<<middle+EPS<<"\n";
``````
xg[], yg[] are the positions of gophers, xh[], yh[] are the positions of holes.

Assume Bipartite(); is a function that calc max bipartite matching
hypot(x, y) = sqrt(x*x+y*y);
intially start = 0;
end = largest distance between (xg, yg[j]) for all i, j.
i try it once end = 1000000.. ### So many WA's in this prob

Posted: Mon Feb 05, 2007 11:00 pm
I am doing bin search on distance and running mbm. I'm getting wa in this.

Code: Select all

``````#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define NIL -1
#define MAXN 110

typedef struct Point_
{
double x,y;
} Point_;

double maxDis;
int Match[MAXN];
int v,M,N;
double W[MAXN][MAXN];
bool visited[MAXN];
Point_ field[MAXN];

bool augment(int u)
{
int next;
if( u == -1 )
return true;

for( int i = 0; i < adj[u].size(); i++ )
{
if( !visited[next] )
{
visited[next] = true;
if(augment(Match[next]))
{
Match[next] = u;
return true;
}
}
}

return false;
}

int MBM(double w)
{
int i,match,j;

memset(Match,NIL,sizeof(Match));

for( i = 1; i <= M; i++ ) adj[i].clear();

for( i = 1; i <= M; i++ )
{
for( j = M + 1; j < N + M + 1; j++ )
{
if( W[i][j] <= w ) adj[i].push_back(j);
}
}

match = 0;

for( i = 1; i <= M; i++ )
{
memset(visited,false,sizeof(visited));
if( augment(i) )
match++;
}

return match;
}

void buildGraph()
{
int i,j;
v = N + M + 2;
maxDis = -1;

for( i = 1; i <= M; i++ )
{
for( j = M + 1; j < N + M + 1; j++ )
{
W[i][j] = sqrt((field[i].x - field[j].x) * (field[i].x - field[j].x) + (field[i].y - field[j].y) * (field[i].y - field[j].y) );
if( maxDis < W[i][j] )
maxDis = W[i][j];
}
}

}

int main()
{
int i,K,T,caseno,m;
double lo,hi,mid;

//freopen("C:\\4.txt","rb",stdin);

scanf("%d",&T);

for( caseno = 1; caseno <= T; caseno++ )
{
scanf("%d %d %d",&M,&N,&K);

for( i = 1; i <= M; i++ ) scanf("%lf %lf",&field[i].x,&field[i].y);
for( i = M + 1; i < M + N + 1; i++ ) scanf("%lf %lf",&field[i].x,&field[i].y);

printf("Case #%d:\n",caseno);
if( M == K )
{
printf("0\n\n");
continue;
}

buildGraph();

m = MBM(maxDis);
if( m < M - K )
{
continue;
}

lo = 0,hi = maxDis;

while( fabs(lo - hi) > 1e-7 )
{
mid = (lo + hi) / 2;
m = MBM(mid);
if( m >= M - K ) hi = mid;
else lo = mid;
}

double mm = 1000.0;
mid = (int)(mid * mm + 0.5) / mm;
printf("%.3lf\n\n",mid);
}

return 0;
}
``````
Any suggetions,I/O.....
plz hlp.

### Re: 10804 - Gopher Strategy

Posted: Fri Apr 03, 2009 12:11 pm
how if m = 0 or n = 0? What should be output? Too bad or 0.000?
Also how if m = k?
Those are too tricky for me. I've getting WA too many times...
Any help wanted........

### Re: 10804 - Gopher Strategy

Posted: Sat Apr 04, 2009 12:22 am
If m=0 or m=k or (n=0 and m=0), the answer is 0.000, of course.

### Re: 10804 - Gopher Strategy

Posted: Sat Apr 04, 2009 3:00 pm
Yeah, finally I managed to get AC I just changed the binary search to work on the sorted distance array instead directly on distance.
Maybe previously I had floating point problems.
Anyway, thanx all for helping me...