142 - Mouse Clicks

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

142 WA!!:-((

Post by Karthekeyan »

I am getting WA for this code....
This is how i proceed...
I store the icon coordinates and the region coordinates in two arrays separately...whenever a mouse click happens, I store the icon(/icons if there are many at the same distance) that is closest to the mouse click in iconposs array....then i check if this click falls inside some region....if so, i find the latest of all regions under which this click falls....i print the region whenever the click falls under a region...else i print all the closest icons....what's wrong with this??

Code: Select all

look at the modified code below
Last edited by Karthekeyan on Thu Dec 29, 2005 8:46 am, edited 1 time in total.
Karthe
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Your program fails this test:

Code: Select all

I 0 0
I 0 100
I 100 100
I 100 0
R 80 80 120 120
M 50 50
#
Did you read the other ***very recent*** thread on this problem?
Obviously, 1 2 3 4 isn't the correct answer, for the reason I described there.
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

Thanks a lot. I will check it out. As for the use of floating point numbers, it is only used to calculate the distance of the mouse click from an icon using sqrt function and I don't see any way to avoid that completely though.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Simply don't compute the square roots.
sqrt() is a strictly increasing function, so it has the properties:
a) sqrt(x)=sqrt(y) if and only if x=y, and
b) sqrt(x)<sqrt(y) if and only if x<y.
Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan »

here is the modified code taking care of the test case you gave above....
help me please

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
struct region
{
				int tlx,tly,brx,bry;
				char regname;
};
struct icon
{
				int x,y;
				int icno;
				int mark;
};
struct possibs
{
				int icno;
				int no;
				char regname;
};
void print(int a)
{
				int n=a;
				int noofdigits=0;
				while(n!=0)
				{
								n/=10;
								noofdigits++;
				}
				if(noofdigits==1)
								cout<<"  "<<a;
				else if(noofdigits==2)
								cout<<" "<<a;
				else
								cout<<a;
}
main()
{

				vector<region> regs;
				char regionname='A';
				vector<icon> icons;
				int iconno=1;
				char ch;
				while(cin>>ch)
				{
								if(ch=='#')
												break;
								if(ch=='I')
								{
												icon temp;
												cin>>temp.x>>temp.y;
												temp.icno=iconno;
												temp.mark=0;
												icons.push_back(temp);
												iconno++;
								}
								else if(ch=='R')
								{
												region temp;
												cin>>temp.brx>>temp.bry>>temp.tlx>>temp.tly;
												int n=icons.size();
												for(int i=0;i<n;i++)
												{					
																int tlx,tly,brx,bry,mx,my;
																tlx=temp.tlx;
																tly=temp.tly;
																brx=temp.brx;
																bry=temp.bry;
																mx=icons[i].x;
																my=icons[i].y;

																if((mx>=brx && mx<=tlx)&&(my>=bry && my<=tly))
																				icons[i].mark=1;
												}
												temp.regname=regionname;
												regs.push_back(temp);
												regionname++;
								}
								else if(ch=='M')
								{
												int mx,my;
												vector<possibs> iconposs;
												possibs regposs;
												regposs.regname='%';

												cin>>mx>>my;
												int ni=icons.size();
												int nr=regs.size();
												long int distance=(long int)1e20;
												for(int i=0;i<ni;i++)
												{
																if(icons[i].mark)
																				continue;
																long int tempdt;
																tempdt=((mx-icons[i].x)*(mx-icons[i].x)+(my-icons[i].y)*(my-icons[i].y));
																if(tempdt<distance)
																{
																				iconposs.clear();
																				possibs temp;
																				temp.icno=icons[i].icno;
																				temp.regname='$';
																				temp.no=i;
																				iconposs.push_back(temp);
																				distance=tempdt;
																}
																else if(tempdt==distance)
																{
																				possibs temp;
																				temp.icno=icons[i].icno;
																				temp.regname='$';
																				temp.no=i;
																				iconposs.push_back(temp);
																				distance=tempdt;

																}
												}
												for(int i=0;i<nr;i++)
												{
																int tlx,tly,brx,bry;
																tlx=regs[i].tlx;
																tly=regs[i].tly;
																brx=regs[i].brx;
																bry=regs[i].bry;

																if((mx>=brx && mx<=tlx)&&(my>=bry && my<=tly))
																{
																				if(regposs.regname<regs[i].regname)
																				{
																								possibs temp;
																								temp.icno=0;
																								temp.regname=regs[i].regname;
																								temp.no=i;
																								regposs=temp;
																				}
																}
												}
												if(regposs.regname!='%')
																cout<<regs[regposs.no].regname<<endl;
												else
												{
																int n=iconposs.size();
																for(int i=0;i<n;i++)
																{
																				print(iconposs[i].icno);
																}
																cout<<endl;
												}

								}
				}	
}
Karthe
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

I modified the test case given by mf to this:

Code: Select all

I 0 0
I 0 100
I 100 0  
R 80 80 120 120
I 100 100
M 50 50
#
The correct output is still the same as the test case give by mf, which is:

Code: Select all

  1  2  3
but your code prints

Code: Select all

  1  2  3  4
Try to check whether an icon is visible after you have read all the icon and region data, and keep track of the visibility of icons before processing
each mouse click.

Also, see this thread:
http://online-judge.uva.es/board/viewtopic.php?t=9576
Last edited by chunyi81 on Sun Jan 01, 2006 3:52 pm, edited 1 time in total.
Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan »

Code: Select all

I 0 0
I 0 100
I 100 0 
R 80 80 120 120
I 100 100
M 50 50
# 
Answer is

Code: Select all

  1  2  3
and not

Code: Select all

  1  2  4
as posted by chunyi81...
and i got my code accepted....very silly error....
Karthe
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

I have corrected the test case to avoid further confusion. Thanks to Karthekeyan for pointing out the error.
farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

please please help(142)

Post by farzane »

why WA:

Code: Select all

//Mouse Click
//#include<fstream.h>
#include<math.h>
#include<iostream.h>
#include<stdio.h>

long int reginNo=0,iconNo=0,name=0,ans[25],ansNo;
long int regin[50][4],icon[25][2],x,y,iconname[50];
char c;

int clickregin(int i){
  if(x>=regin[i][0])
    if(x<=regin[i][2])
      if(y>=regin[i][1])
	if(y<=regin[i][3])
	  return 1;
return 0;
}

void answer(){
  long int i;
  for(i=reginNo-1;i>=0;i--)
   if(clickregin(i)==1){
      cout<<char('A'+i)<<endl;
      return;
   }
  ansNo=0;
  double dis,less=10000;
  for(i=0;i<iconNo;i++){
    dis=(x-icon[i][0])*(x-icon[i][0])+(y-icon[i][1])*(y-icon[i][1]);
    dis=sqrt(dis);
    if(dis<less){
      ansNo=1;
      ans[0]=i;
      less=dis;
    }else
    if(dis==less){
     ans[ansNo]=i;
     ansNo++;
    }
  }
  for(i=0;i<ansNo;i++)
     printf("%3d",iconname[ans[i]]+1);
  cout<<endl;
}


void main(){
iconNo=reginNo=0;
//ifstream cin("142.txt");
cin>>c;
while(c!='M'){
 if(c=='I') {
    
	 cin>>x>>y;
c=true;
int i;
for(i=0;i<reginNo;i++){
	if(x>=regin[i][0])
    if(x<=regin[i][2])
      if(y>=regin[i][1])
	   if(y<=regin[i][3])
	      c=false;
}


if(c){
	icon[iconNo][0]=x;
	icon[iconNo][1]=y;
    iconname[iconNo]=name;
    iconNo++;
 }
 name++; 
 
 }


 if(c=='R'){
    cin>>regin[reginNo][0]>>regin[reginNo][1];
    cin>>regin[reginNo][2]>>regin[reginNo][3];
    reginNo++;
 }
 cin>>c;
}
while(c!='#'){
  cin>>x>>y;
  answer();
  cin>>c;
}

}
fayyazkl
New poster
Posts: 11
Joined: Thu Mar 16, 2006 8:02 am
Location: Lahore, Pakistan

RUN TIME ERROR :)

Post by fayyazkl »

HI ALL!

I HAVE READ ALL THE POSTS. ALL IMPROVED MY PROGRAM SO FAR. I HAVE ONE THING DIFFERENT FROM ALL OTHERS. I START PRINTING ANY THING AFTER THE USER HAS INPUT THE '#' CHARACTER. THERE IS NO SUCH SPECIFICATION FORBIDDING THIS. CAN ANY BODY HELP ME ON THAT.

is it okay to store all mouse clicks in an array and start printing after receiving a '#' character. Please help i am getting RE always.

thanx
There are 10 types of people. Those who can read binary and those who cant ;)
http://acm.uva.es/problemset/usersjudge.php?user=37504
fayyazkl
New poster
Posts: 11
Joined: Thu Mar 16, 2006 8:02 am
Location: Lahore, Pakistan

WA in 142 :)

Post by fayyazkl »

I have changed my code to the form that it processes each mouse click as it is entered and now i am getting WA!!

i hate to post code but got no choice. Please help!!!


# include <iostream>
# include <cmath>
# include <iomanip>
//# include <fstream>

using namespace std;

struct icon
{
int x,y;
};

struct region
{
int left, top, right, bottom;
};


main ()
{
struct icon ic[55];
struct icon mouse;
struct region rg[30];
char type;
int i=0,r=0,m=0;

// ifstream in ("d:\\click.in");

while (cin >> type)
{
if (type == '#')
break;

if ( type == 'I')
{
cin >> ic.x >> ic.y;
i++;
}

else if (type == 'R')
{
cin >> rg[r].left >> rg[r].top >> rg[r].right
>> rg[r].bottom;
r++;
}

else if (type == 'M')
{
cin >> mouse.x >> mouse.y;


int flag = 0;

for (int b=r-1; b>=0; --b)
{
if ( mouse.x >= rg.left &&
mouse.x <= rg.right && mouse.y >= rg.top
&& mouse.y <= rg.bottom )
{
char temp = 'A'+b;
cout << temp << endl;

flag = 1;
break;
}
}

if (flag == 0) // if not found in a region look for icon
{
double dis=0,mind=1000;
int sub;


for (int a=0; a<i; a++) // using distance formula
{

for (int h=0; h<r; h++) // see whether an icon is
{ // visible
if ( ic[a].x >= rg[h].left &&
ic[a].x <= rg[h].right && ic[a].y >= rg[h].top
&& ic[a].y <= rg[h].bottom )
{
ic[a].x = 1000;
ic[a].y = 1000;
}

}

if (ic[a].x != 1000 || ic[a].y != 1000)
{
int t = (ic[a].x - mouse.x);
t = t*t;

int t1 = ic[a].y - mouse.y;
t1 = t1*t1;

dis = t + t1;
dis = sqrt(dis);

if ( dis - mind < 0.00 )
{
mind = dis;
sub = a+1;
}
}
}

cout << setw(3) << sub;

for (int d=0; d<i; d++)
{
int p = ic[d].x-mouse.x;
p = p * p;
int p1 = ic[d].y-mouse.y;
p1 = p1*p1;

p = p+p1;
double s = sqrt(p);
int sq = s;

int min = mind;


if (min == sq && d+1 != sub)
cout << setw(3) << d+1;

}

cout << endl;

}

}


}



return 0;
}
There are 10 types of people. Those who can read binary and those who cant ;)
http://acm.uva.es/problemset/usersjudge.php?user=37504
andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft »

Hello people!
I have read most of the useful threads about this problem, but still I am getting WA.
I have learned that there are more than one test case in the input.
And I fixed it and don't know where may be my other mistake(s).

Code: Select all

program Project2;

{$APPTYPE CONSOLE}
{$R-}{$S-}{$Q-}

uses
  SysUtils;

type
  point = record
    x: integer;
    y: integer;
  end;
  rect = record
    x1: integer;
    y1: integer;
    x2: integer;
    y2: integer;
  end;

function pointInWin (const x,y: integer; const win: rect): boolean;
begin
  pointInWin := ((x>=win.x1) and (y>=win.y1) and (x<=win.x2) and (y<=win.y2));
end;

function dist (const x1,y1,x2,y2: integer): integer;
begin
  dist := round(sqrt(sqr(x1-x2)+sqr(y1-y2)))
end;

var
  win: array ['A'..'Z'] of rect;
  ico: array [1..100] of point;
  i,j,k,l,m,ni,min: integer;
  nc,c: char;
  fl: boolean;
  x,y: integer;

function iconOnTop (const x,y: integer): boolean;
var
  c: char;
begin
  for c:='A' to nc do
    if pointInWin (x,y,win[c]) then
    begin
      iconOnTop := false;
      exit
    end;
  iconOnTop := true
end;

begin
while not eof do
begin
  nc := char(ord('A')-1);
  ni := 0;
  while true do
  begin
    read (c);
    if c='I' then
    begin
      inc (ni);
      readln (ico[ni].x,ico[ni].y);
    end
    else if c='R' then
    begin
      nc := char(ord(nc)+1);
      readln (win[nc].x1,win[nc].y1,win[nc].x2,win[nc].y2)
    end
    else if c='M' then
    begin
      readln (x,y);
      fl := false;
      for c:=nc downto 'A' do
        if pointInWin (x,y,win[c]) then
        begin
          writeln (c);
          fl := true;
          break
        end;
      min := 6000;
      if fl then continue;
      for i:=1 to ni do
        if iconOnTop(ico[i].x,ico[i].y) and (dist(ico[i].x,ico[i].y,x,y) < min) then
          min := dist(ico[i].x,ico[i].y,x,y);
      if min <> 6000 then
        for i:=1 to ni do
          if (dist(ico[i].x,ico[i].y,x,y) = min) and iconOnTop (ico[i].x,ico[i].y) then
            write (i:3);
      writeln
    end
    else break;

  end;

end;


end.

Thank you
Now I lay me down to sleep...
my profile
imrankane2005
New poster
Posts: 4
Joined: Mon Aug 13, 2007 3:12 pm

WA

Post by imrankane2005 »

i m frustrated...
i hav chek all the hint given in the forum but still i m getting WA
here`s my code......

#include <cstdlib>
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
using namespace std;
struct ireg
{
int no;
int x;
int y;
};
int main(int argc, char *argv[])
{
char reg[500][500];
ireg icon[25000];
vector <int> v1;
string inp;
getline(cin,inp);
char inst;
int x1,y1,x2,y2,i;
int cont=0;
char cc='A';
int ic=0;
inst=inp[0];
int dist,smx,smy;
for(int j=0;j<500;j++)
for(int k=0;k<500;k++)
reg[j][k]=-1;
while(inp!="#")
{
v1.clear();
x1=0;y1=0;x2=0;y2=0;
inst=inp[0];
if ((toupper(inst)=='I')||(toupper(inst)=='R'))
{
i=0;
while(!isdigit(inp))
i++;
while(isdigit(inp))
{
x1=x1*10+inp-48;
i++;
}
while(!isdigit(inp))
i++;
while(isdigit(inp))
{
y1=y1*10+inp-48;
i++;
}
if (toupper(inst)=='R')
{
while(!isdigit(inp))
i++;
while(isdigit(inp))
{
x2=x2*10+inp-48;
i++;
}
while(!isdigit(inp))
i++;
while(isdigit(inp[i]))
{
y2=y2*10+inp[i]-48;
i++;
}
}
if (toupper(inst)=='I')
{
icon[ic].x=x1;
icon[ic].y=y1;
icon[ic].no=ic+1;
ic++;
}
else
{
for(int j=x1;j<=x2;j++)
for(int k=y1;k<=y2;k++)
{
reg[j][k]=cc;
}
cc++;
}
}
if (toupper(inst)=='M')
{
i=0;
while(!isdigit(inp[i]))
i++;
while(isdigit(inp[i]))
{
x1=x1*10+inp[i]-48;
i++;
}
while(!isdigit(inp[i]))
i++;
while(isdigit(inp[i]))
{
y1=y1*10+inp[i]-48;
i++;
}
dist=500000;
int distnc;
int con=0;
for(int j=0;j<ic;j++)
{
if (reg[icon[j].x][icon[j].y]!=-1)
continue;
if ((icon[j].x==x1)&&(icon[j].y==y1))
{
v1.clear();
v1.push_back(icon[j].no);
con=1;
break;
}
distnc=((icon[j].x-x1)*(icon[j].x-x1))+((icon[j].y-y1)*(icon[j].y-y1));
if (distnc<dist)
{
dist=distnc;
v1.clear();
v1.push_back(icon[j].no);
}
else
if (distnc==dist)
{
v1.push_back(icon[j].no);
}
}
char cr;
cr='\n';
if (con==0)
{
cr=reg[x1][y1];
if ((int)cr==-1)
con=1;
}
if (con==1)
{for(int j=0;j<v1.size();j++)
cout<<" "<<v1[j];
}else
cout<<cr;
cout<<endl;
}
getline(cin,inp);

}
return 0;
}

plzzz help me to point out the error...
imrankane2005
New poster
Posts: 4
Joined: Mon Aug 13, 2007 3:12 pm

Post by imrankane2005 »

plzzzz don`t be so harsh atleast provid sum more test cases.........
imrankane2005
New poster
Posts: 4
Joined: Mon Aug 13, 2007 3:12 pm

Post by imrankane2005 »

plzzz help me i hav been stuck here fr abt 3-4 days....
i m desperate fr help becaz i don`t see any error in my code....
Post Reply

Return to “Volume 1 (100-199)”