Page 1 of 1

155 - All Squares

Posted: Sun Feb 23, 2003 2:49 am
by kenshin_kudo
Does anybody know why I got compile error for this one? It worked on my machine... :-?
[java]
import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

static int x;
static int y;
static int level;
static int square;
static int sx;
static int sy;
static int p;
static int k;

public static void main(String args[]) throws Exception {
String s;
while(!((s=ReadLn(255)).trim()).equals("0 0 0")) {
StringTokenizer st=new StringTokenizer(s);
int largest=Integer.parseInt(st.nextToken());
x=Integer.parseInt(st.nextToken());
y=Integer.parseInt(st.nextToken());
int tmp=0;
level=0;
square=0;
while(tmp<largest) {
tmp=(int)Math.pow(2,level++);
}
level--;
sy=1025;
sx=1025;
k=largest;
chkSquare(level);
System.out.println(padd(square));
}
}

public static String padd(int n) {
String s=new Integer(n).toString();
int l=s.length();
//System.out.println(l);
String r="";
for(int i=0;i<(3-l);i++) {
r+=" ";
}
r+=s;
return r;

}

public static void chkSquare(int l) {
p=k;
if(p==0) {
return;
}
if((x>=(sx-p))&&(x<=(sx+p))) {
if((y>=(sy-p))&&(y<=(sy+p))) {
square++;
}
}

if((x<=sx)&&(y<=sy)) {
sx=sx-p;
sy=sy-p;
k=k/2;
chkSquare(--l);
}
else if((x>=sx)&&(y<=sy)) {
sx=sx+p;
sy=sy-p;
k=k/2;
chkSquare(--l);
}
else if((x<=sx) &&(y>=sy)) {
sx=sx-p;
sy=sy+p;
k=k/2;
chkSquare(--l);
}
else if((x>=sx)&&(y>=sy)) {
sx=sx+p;
sy=sy+p;
k=k/2;
chkSquare(--l);
}

}
}
[/java]

155 All Squares

Posted: Mon Jan 31, 2005 9:48 pm
by superfathy
In problem 155, where is the origin of the grid (0,0)?
Thanks in advance.... 8)

Posted: Thu Feb 10, 2005 7:26 pm
by jonaskoelker
upper left. Says so in the problem.

Posted: Sat Apr 16, 2005 3:34 pm
by I LIKE GN
Hello
all
I have just got a WA
any body please give me some I/O
one thing... i use the corner coordinates as
( where cx and cy initially set to (1024, 1024) and
k is as in the description )
/* upper left corner */
ux = (cx-k), uy = (cy-k);

/* upper right corner */
x = (cx+k), y = (cy-k);

/* lower left corner */
x = (cx-k), y = (cy+k);

/* lower right corner */
lx = (cx+k), ly = (cy+k);
and also

Code: Select all

if( (X >=ux && X<= lx) && ( Y >=uy && Y <= ly) ){
	Global_Count++;
}

waaaaaaaaaa

Posted: Fri Aug 26, 2005 11:50 am
by I LIKE GN
well i post my WA soln. here :wink:

Code: Select all

ACCed 
cut off.......
here is a bug(i think)

Code: Select all

if( (k/2)>=1 ){
it should be

Code: Select all

if( k>1 ){
but then the sample I/O is no longer Okk :( ...
i don know how to fix it. help please...
thx...

helloooooooooooooooooooo!!!!!!!!!!!

Posted: Fri Sep 02, 2005 12:14 pm
by I LIKE GN
help meeeeeeeeee!!!!!!!!!!!!!!

HELLLLLLLLOOOOOOOOOOOO!!!!!!

Posted: Tue Sep 06, 2005 10:41 pm
by I LIKE GN
hello please help meeeeeeeee!!!!!!!!!!!!!!!!!
tell me where amm i wrong...
or would me mail me a soln?????????????

155

Posted: Thu Jan 25, 2007 4:10 pm
by Viswanathan V
I have a doubt in prob 155...
my solution is recursive with 4 recursive calls for the 4 ends of the square.

I however get a WA.I have right aligned my output too.

As a sample test case i use here
I/P:
500 113 941
20 1020 1020
300 500 500
200 150 350
0 0 0

O/p is
5
1
2
0

can any one tell me where i have made a mistake.If you have a test case that you feel can make a difference to the logic of my program can you please reply.
thanks in advance.

Posted: Fri Jan 26, 2007 2:57 am
by emotional blind
My Accepted code ouputs 3 for second case.

Posted: Fri Jan 26, 2007 4:09 am
by Viswanathan V
Hi,
I got the answer accepted.
The problem with my code was that i failed to initialize one center variable after the recursion returned.
Thanks,
Viswanathan

Re: 155

Posted: Mon Feb 08, 2010 12:11 am
by gaber
i solved that problem by recursion but i dont know y it doesnt work .
here is my code any one find the mistake please tell me and thanks in advance.


//still wrong
import java.util.Scanner;

class point
{
double x;
double y;
point(double i,double j)
{
x = i;
y = j;
}
}
public class allsquares {

static point p;
static int n = 0;
public static void solve(point center,int k)
{
point lt = new point(center.x-k-.5,center.y-k-.5);
point rt = new point(center.x-k-.5,center.y+k+.5);
point lb = new point(center.x+k+.5,center.y-k-.5);
point rb = new point(center.x+k+.5,center.y+k+.5);
if(p.x>=lt.x&&p.x<=lb.x&&p.y>=lt.y&&p.y<=rt.y) n++;

if(k==1)
{
return;
}
else
{
solve(lt,k/2);
solve(rt,k/2);
solve(lb,k/2);
solve(rb,k/2);
}
}
public static void main(String[] args) {


point center = new point((double)2049/2,(double)2049/2);
Scanner s = new Scanner(System.in);
int k;
while(s.hasNext())
{
k = s.nextInt();
if(k==0) break;
n = 0;
p = new point(s.nextDouble(),s.nextDouble());
solve(center,k);
System.out.println(n);
}
}

}

Re: 155

Posted: Wed May 28, 2014 11:53 pm
by Repon kumar Roy
I cannot undestand the output of my program.. It is returning a huge number.....

Code: Select all


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>

using namespace std;

/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 1000000007

/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))



ll center_x, center_y,ans;
void circle(ll x, ll y, ll rad)
{
    if(rad<3) return;
    if(x+rad<=2048 && x-rad>=0 && y+rad<=2048 && y-rad >=0) {
        ans++;
        
    }
    
    if(x+rad<=2048 && y+rad <=2048)circle(x+rad, y+rad, rad/2);
    if(x-rad>=0 && y+rad <=2048)circle(x-rad, y+rad, rad/2);
    if(x+rad<=2048 && y-rad >=0)circle(x+rad, y-rad, rad/2);
    if(x-rad>=0 && y-rad >=0)circle(x-rad, y-rad, rad/2);
    return;
    
    
}
int main()
{
    ll k;
    while (cin>>k>>center_x>>center_y) {
        ans=0;
        circle(center_x, center_y, k);
        //cout<<ans<<endl;
        printf("%3lld\n",ans);
    }
    return 0;
}