142 - Mouse Clicks

[asmaamagdi]

You shouldn't worry about printing a blank line here:

for this test case does not select anything at all since it does not select the only region in this test case and the only icon the mouse click can select is not visible.

as the problem description says that:

There will always be at least one visible icon

[xtremedreamer]

I am getting wrong answer again & again. Anybody plz provide some tricky inputs:
Here is my code:

Code: Select all

#include <stdio.h>
#include <memory.h>

int EuclidDistSqre( int x1, int y1, int x2, int y2 ){
	return ((x1 - x2)*(x1 - x2)+(y1 - y2)*(y1 - y2));
}

bool isObscuredIcon( int region[250][4], int ri, int iconrow, int iconcol) {
	for ( int i = 0; i < ri; i++){
		if ((iconrow >= region[i][0] && iconrow <= region[i][2]) && (iconcol >= region[i][1] && iconcol <= region[i][3]))
			return true;
	}
	return false;
}

int main(){
	
	int Region[250][4], Icon[500][2], Mouse[2], Ri = 0, Ii = 0, dist[2500], minDist, i , j;
	char c[10000];
	bool obscuredFlag[500], firstMouseEvent = false;
	memset(obscuredFlag, 1, 500*sizeof(bool));
	//freopen("M:\\Documents and Settings\\prince\\Desktop\\142.txt","r",stdin);
	while (scanf("%s",c) != EOF){
		if (c[0] == '#'){
			Ii = Ri = 0;
			memset(obscuredFlag, 1, 500*sizeof(bool));
			firstMouseEvent = false;
			continue;
		}
		if (c[0] == 'I'){
			scanf("%d%d",&Icon[Ii][0],&Icon[Ii++][1]);
		}
		else if (c[0] == 'R'){
			scanf("%d%d%d%d",&Region[Ri][0],&Region[Ri][1],&Region[Ri][2],&Region[Ri++][3]);
		}
		else if(c[0] == 'M'){ 
			scanf("%d%d",&Mouse[0],&Mouse[1]);
			bool flag = false;
			if (!firstMouseEvent){
				firstMouseEvent = true;
				for ( i = 0; i < Ii; i++){
					if (!isObscuredIcon(Region,Ri,Icon[i][0],Icon[i][1]))
						obscuredFlag[i] = false;
				}
			}
			for ( i = Ri - 1; i >= 0; i--){
				if ((Mouse[0] >= Region[i][0] && Mouse[0] <= Region[i][2]) && (Mouse[1] >= Region[i][1] && Mouse[1] <= Region[i][3])){  
					printf("%c",65+i);
					flag = true;
					break;
				}
			}
			
			
			if (!flag){
				minDist = 1000000;
				for (i = 0; i < Ii; i++){
					dist[i] = EuclidDistSqre( Mouse[0], Mouse[1], Icon[i][0], Icon[i][1] );
					if(minDist > dist[i])
						minDist = dist[i];
				}
				

				for (j = 0; j < i; j++){
					if (dist[j] == minDist && !obscuredFlag[j]){
						printf("%3d",j+1);
					}
				}
			}
			printf("\n");

		}
	}
	return 0;
}

[Articuno]

Can someone help me please? I am getting WA. Some test cases will be very helpful.
Is it a multiple input problem or will there be only one test input?
Please someone reply. Thanks in advance.

[mf]

Is it a multiple input problem or will there be only one test input?

Input is exactly what the problem statement says it is - one input set, terminated by #.

Some test cases will be very helpful.

If you provide the input, I can run my accepted program on it, and post the output here.

[choby]

please can anyone tell me where is my error?? i'm getting wa twice =(

Code: Select all

import java.util.*;

class Main {
    static Scanner buffer=new Scanner(System.in);
    //icono auxi;
    
    static String convierte(int i)
    {
        if(i<10) return "  "+i;
        else return " "+i;
    }

    public static void main(String[] args)
    {
        
        String tipo;
        //int i1,i2,i3,i4;
        int posi,posv;
        Main.icono auxi;
        Main.ventana auxv;
        posi=posv=0;
        Main.ventana ventanas[]=new ventana[30];
        //ventanas[0]=null;
        Main.icono iconos[]=new icono[60];
        //iconos[0]=null;
        
        //boolean clicks=false;
        while(true)
        {

            tipo=buffer.next();
            if(tipo.equals("#")) break;
            else if(tipo.equals("I"))
            {
                //System.out.println("Estoy en un icono");
                Main aux=new Main();
                auxi=aux.new icono(buffer.nextInt(),buffer.nextInt());
               //xi=Main.new icono(buffer.nextInt(),buffer.nextInt());

                auxi.numero=1+posi;
               iconos[posi++]=auxi;
               //System.out.println("el valor del icono es "+iconos[posi-1].x+" "+iconos[posi-1].y);
            }
            else if(tipo.equals("R"))
            {
               //System.out.println("estoy en una region");
                Main aux=new Main();
               auxv=aux.new ventana(buffer.nextInt(),buffer.nextInt(),buffer.nextInt(),buffer.nextInt());
               auxv.letra=(char)('A'+posv);
               ventanas[posv++]=auxv;
            }
            else if(tipo.equals("M"))
            {
                int posX, posY;
                posX=buffer.nextInt();
                posY=buffer.nextInt();
                int elegido=-1;
                for(int i=0; i<posv; i++)
                {
                    if(ventanas[i].dentro(posX, posY))
                    elegido=i;
                }
                if(elegido==-1)
                {
                    double minDistancia=100000.0;
                    for(int i=0; i<posi; i++) minDistancia=Math.min(minDistancia, iconos[i].distancia(posX, posY));
                    for(int i=0; i<posi; i++)
                    {if(iconos[i].distancia(posX, posY)-minDistancia<=0.000000001)
                        System.out.print(convierte(i+1));
                    }
                    System.out.println();
                }
                else
                {
                    System.out.println(ventanas[elegido].letra);
                }
            }
        }

    }


class icono
{
    int x,y;
    int numero;
    public icono(int i, int j)
    {
        this.x=i;
        this.y=j;
    }

    double distancia(int i, int j)
    {
        return Math.sqrt(((this.x-i)*(this.x-i)+(this.y-j)*(this.y-j))*1.0);
    }
}

class ventana
{
    int xo,xf,yo,yf;
    char letra;
    public ventana(int i1, int j1, int i2, int j2)
    {
        this.xo=i1;
        this.xf=i2;
        this.yo=j1;
        this.yf=j2;
    }

    boolean dentro(int x, int y)
    {
        if(this.xo<=x && this.xf>=x && this.yo<=y && this.yf>=y) return true;
        return false;
    }
}



}

[Amos]

I try above test cases and it's as same as AC outputs, can anyone tell me why I still get WA?

My Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void CreateIcon(int, char*);
void CreateArea(int, char*);
void CreateMouse(int, char*);
void IconInArea(int, int);
int MouseInArea(int, int);
void MouseInIcon(int, int);

struct Icon
{
int x, y;
int visible;
};

struct Area
{
int x1, y1, x2, y2;
};

struct Mouse
{
int x, y;
};


struct Icon icon[50];
struct Area area[25];
struct Mouse mouse[100000];

int main()
{
int i = 0, j = 0, k = 0;
char str[100];
gets(str);
while (str[0] != '#')
{
if (str[0] == 'I')
{
CreateIcon(i, str);
i++;
}
else if (str[0] == 'R')
{
CreateArea(j, str);
j++;
}
else if (str[0] == 'M')
{
CreateMouse(k, str);
k++;
}
gets(str);
}
int p;
for (p=0;p<i;p++)
{
IconInArea(p, j);
}
for (p=0;p<k;p++)
{
if (!MouseInArea(p, j))
{
MouseInIcon(p, i);
}
}
return 0;
}

void IconInArea(int index, int area_size)
{
int i;
for (i=0;i<area_size;i++)
{
if ((area.x1 <= icon[index].x && area.x2 >= icon[index].x) && (area.y1 <= icon[index].y && area.y2 >= icon[index].y))
{
icon[index].visible = 0;
break;
}
}
}

int MouseInArea(int index, int area_size)
{
int i;
for (i=area_size-1;i>=0;i--)
{
if ((area.x1 <= mouse[index].x && area.x2 >= mouse[index].x) && (area.y1 <= mouse[index].y && area.y2 >= mouse[index].y))
{
printf("%c\n", i+65);
return 1;
}
}
return 0;
}

void MouseInIcon(int index, int icon_size)
{
int i;
int click[50];
int min = 10000000, sum = 0;
for (i=0;i<icon_size;i++)
{
if (icon.visible == 1)
{
sum = pow((icon.x - mouse[index].x), 2) + pow((icon[i].y - mouse[index].y), 2);
if (sum < min)
min = sum;
click[i] = sum;
}
}
for (i=0;i<icon_size;i++)
{
if (click[i] == min)
printf("%3d", i+1);
}
printf("\n");
}

void CreateIcon(int i, char *str)
{
int j = 1, k = 0;
int x;
int temp[2];
int tag;
while (str[j] == ' ' && str[j] != '\0')
{
x = 0;
tag = 0;
j++;
while (str[j] != ' ' && str[j] != '\0')
{
tag = 1;
x = x*10 + (str[j] - '0');
j++;
}
if (tag)
{
temp[k] = x;
k++;
}
}
icon[i].x = temp[0];
icon[i].y = temp[1];
icon[i].visible = 1;
}

void CreateArea(int i, char *str)
{
int j = 1, k = 0;
int x;
int temp[4];
int tag;
while (str[j] == ' ' && str[j] != '\0')
{
x = 0;
tag = 0;
j++;
while (str[j] != ' ' && str[j] != '\0')
{
tag = 1;
x = x*10 + (str[j] - '0');
j++;
}
if (tag)
{
temp[k] = x;
k++;
}
}
area[i].x1 = temp[0];
area[i].y1 = temp[1];
area[i].x2 = temp[2];
area[i].y2 = temp[3];
}

void CreateMouse(int i, char *str)
{
int j = 1, k = 0;
int x;
int temp[2];
int tag;
while (str[j] == ' ' && str[j] != '\0')
{
x = 0;
tag = 0;
j++;
while (str[j] != ' ' && str[j] != '\0')
{
tag = 1;
x = x*10 + (str[j] - '0');
j++;
}
if (tag)
{
temp[k] = x;
k++;
}
}
mouse[i].x = temp[0];
mouse[i].y = temp[1];
}

I need your help, thanks very much!!

[Sebas]

Hello I dont get why my program trows segmentation fault, When I try to debug it is ok....
thanks

Here is the code:

Code: Select all

#include <iostream>
#include <deque>
#include <math.h>

struct region {
	float x,y,x1,y1;
	char nombre;
	region(float a,float b,float c,float d,char e){
		x=a; y=b; x1=c; y1=d;
		e=nombre;
	}
	
	
};

struct icono{
	float x,y;
	int nombre;
	icono(int a,int b,int c){x=a; y=b; nombre=c;}

};

typedef std::deque<region*> regiones;
typedef std::deque<icono*> iconos;
typedef std::deque<region*>::iterator it_regiones;
typedef std::deque<icono*>::iterator it_iconos;

regiones m_regiones;
iconos m_iconos;
it_regiones it_m_regiones;
it_iconos it_m_iconos;
char lista[30]="abcdefghijklmmnopqrstuvwxyz";

int main (int argc, char * const argv[]) {
	float alfa,beta,gama,delta;
	float max_iconos=sqrt(pow(499,2)+pow(499,2));
	int resultados=0;
	int contador_r=0;
	int contador_i=0;
	char cod[60];
	std::deque<int> resul_iconos;
	bool x=0;
	scanf("%s",cod);

		while(std::strcmp(cod,"#")!=0){
			if (strcmp(cod,"R")==0) {
				scanf("%f",&alfa);
				scanf("%f",&beta);
				scanf("%f",&gama);
				scanf("%f",&delta);
				region *temp=new region(alfa,beta,gama,delta,lista[contador_r]);
				m_regiones.push_front(temp);
				contador_r++;
			}
			
			if (strcmp(cod, "I")==0) {
				scanf("%f",&alfa);
				scanf("%f",&beta);
				icono *temp1=new icono(alfa,beta,contador_i);
				m_iconos.push_back(temp1);
			}
			if (strcmp(cod,"M")==0) {
				resultados++;
				region*t1=0;
				scanf("%f",&alfa);
				scanf("%f",&beta);
				for (it_m_regiones=m_regiones.begin();it_m_regiones!=m_regiones.end();it_m_regiones++) {
					if((*it_m_regiones)->x<=alfa&&(*it_m_regiones)->x1<=alfa &&(*it_m_regiones)->y<=beta&&(*it_m_regiones)->y1<=beta){
					
						t1=*it_m_regiones;
						m_regiones.erase(it_m_regiones);
						m_regiones.push_front(*it_m_regiones);
						printf("%s \n",&t1->nombre);
						
						break;
					}
					x=true;
				}
				if (x) {
					
					for (it_m_iconos=m_iconos.begin();it_m_iconos!=m_iconos.end(); it_m_iconos++) {
						float t2=sqrt(pow(2,(*it_m_iconos)->x-alfa)+pow(2,(*it_m_iconos)->y-beta));
						
						if (max_iconos==t2) {
							resul_iconos.push_back((*it_m_regiones)->nombre);
						}
						if (max_iconos>t2) {
							max_iconos=t2;
							resul_iconos.clear();
							resul_iconos.push_back((*it_m_regiones)->nombre);
						}
					
					}
					x=0;
					for (std::deque<int>::iterator it=resul_iconos.begin();it!=resul_iconos.end();it++) {
						printf("%3d",(*it));
					}
					std::cout<<std::endl;
				}
				
				
			}
		
			scanf("%s",cod);
		}
	
	return 0; 
}

Here is the input

Code: Select all

I       216     28
R       22      19      170     102
I       40      150
I       96      138
I       36      193
R       305     13      425     103
I       191     184
I       387     200
R       266     63      370     140
I       419     134
I       170     102
M       50      50
M       236     30
M       403     167
M       330     83
#

[Sebas]

Hi I was testing with the uva bot, and I always get the same results, can anyone tell what is wrong with my program

Code: Select all

#include <iostream>
#include <deque>
#include <math.h>

struct region {
	float x,y,x1,y1;
	char nombre;
	region(float a,float b,float c,float d,char e){
		x=a; y=b; x1=c; y1=d;
		nombre=e;;
	}
	
	
};

struct icono{
	float x,y;
	int nombre;
	icono(int a,int b,int c){x=a; y=b; nombre=c;}

};

typedef std::deque<region*> regiones;
typedef std::deque<icono*> iconos;
typedef std::deque<region*>::iterator it_regiones;
typedef std::deque<icono*>::iterator it_iconos;

regiones m_regiones;
iconos m_iconos;
it_regiones it_m_regiones;
it_iconos it_m_iconos;
char lista[30]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main (int argc, char * const argv[]) {
	float alfa,beta,gama,delta;
	float max_iconos=sqrt(pow(499,2)+pow(499,2));
	int resultados=0;
	int contador_r=0;
	int contador_i=1;
	bool final=0;
	char cod[60];
	std::deque<int> resul_iconos;
	bool x=1;
	scanf("%s",cod);

		while(std::strcmp(cod,"#")!=0){
			if(final) strcpy(cod,"M");
			if (strcmp(cod,"R")==0) {
				scanf("%f",&alfa);
				scanf("%f",&beta);
				scanf("%f",&gama);
				scanf("%f",&delta);
				region *temp=new region(alfa,beta,gama,delta,lista[contador_r]);
				m_regiones.push_front(temp);
				contador_r++;
			}
			
			if (strcmp(cod, "I")==0) {
				scanf("%f",&alfa);
				scanf("%f",&beta);
				icono *temp1=new icono(alfa,beta,contador_i);
				m_iconos.push_back(temp1);
				contador_i++;
			}
			if (strcmp(cod,"M")==0) {
				final=1;
				resultados++;
				region*t1=0;
				scanf("%f",&alfa);
				scanf("%f",&beta);
				for (it_m_regiones=m_regiones.begin();it_m_regiones!=m_regiones.end();it_m_regiones++) {
					if((*it_m_regiones)->x<=alfa&&(*it_m_regiones)->x1>=alfa &&(*it_m_regiones)->y<=beta&&(*it_m_regiones)->y1>=beta){
					
						t1=*it_m_regiones;
						//m_regiones.erase(it_m_regiones);
						//m_regiones.push_front(*it_m_regiones);
						printf("%s \n",&(t1->nombre));
						x=false;
						break;
					}
					
				}
				if (x) {
					
					for (it_m_iconos=m_iconos.begin();it_m_iconos!=m_iconos.end(); it_m_iconos++) {
						float t2=sqrt(pow((*it_m_iconos)->x-alfa,2)+pow((*it_m_iconos)->y-beta,2));
						
						if (max_iconos==t2) {
							resul_iconos.push_back((*it_m_iconos)->nombre);
						}
						if (max_iconos>t2) {
							max_iconos=t2;
							resul_iconos.clear();
							resul_iconos.push_back((*it_m_iconos)->nombre);
						}
					
					}
					
					for (std::deque<int>::iterator it=resul_iconos.begin();it!=resul_iconos.end();it++) {
						printf("%3d",(*it));
					}
					std::cout<<std::endl;
				}
				x=1;
				max_iconos=sqrt(pow(499,2)+pow(499,2));
				
			}
		
			scanf("%s",cod);
		}
	
	
	for (it_m_iconos=m_iconos.begin();it_m_iconos!=m_iconos.end(); it_m_iconos++) {
		delete (*it_m_iconos);
	}
	
	for (it_m_regiones=m_regiones.begin();it_m_regiones!=m_regiones.end();it_m_regiones++) {
		delete (*it_m_regiones);
	}
	
	return 0; 
}

Regards

[happyson10]

Got AC now

[brianfry713]

Input:

Code: Select all

I       383     386
I       277     415
I       293     335
I       386     492
I       149     421
I       362     27
I       190     59
I       263     426
I       40      426
I       172     236
I       211     368
I       67      429
I       282     30
I       362     123
I       67      135
I       429     302
I       22      58
I       69      167
I       393     456
I       11      42
I       229     373
I       421     419
I       284     37
I       198     324
I       315     370
I       413     26
I       91      480
I       456     373
I       362     170
I       496     281
I       305     425
I       84      327
I       336     5
I       346     229
I       313     357
I       124     395
I       82      45
I       314     367
I       434     364
I       43      250
I       87      308
I       276     178
I       288     84
I       403     151
I       254     399
I       432     60
I       176     368
I       239     12
I       226     86
I       94      39
R       295     70      344     368
R       467     101     493     247
R       317     492     483     496
R       301     280     327     401
R       365     189     429     404
R       440     229     491     287
R       97      271     485     285
R       209     427     230     454
R       497     353     497     451
R       306     183     481     471
R       28      371     120     379
R       3       19      370     362
R       208     215     480     239
R       296     223     358     306
R       346     451     441     493
R       379     488     464     496
R       341     350     480     450
R       34      264     250     362
R       487     356     494     383
R       227     365     335     426
R       432     51      441     165
R       275     407     449     408
R       358     395     477     462
R       235     293     453     313
R       143     11      434     299
M       276     404
M       443     263
M       113     38
M       106     340
M       404     318
M       128     188
M       369     417
M       417     496
M       324     243
M       470     183
M       490     499
M       272     225
M       144     90
M       5       139
M       454     286
M       169     82
M       42      464
M       197     7
M       355     304
M       348     111
M       122     328
M       299     343
M       246     68
M       340     422
M       311     310
M       105     301
M       161     230
M       378     305
M       320     236
M       444     126
M       22      465
M       208     416
M       282     258
M       424     137
M       62      124
M       100     36
M       452     399
M       379     50
M       468     71
M       473     131
M       381     430
M       433     394
M       160     163
M       199     481
M       399     496
M       459     273
M       313     168
M       190     95
M       426     466
M       84      340
M       90      184
M       376     42
M       436     107
M       445     256
M       179     418
M       387     412
M       348     172
M       159     9
M       336     210
M       342     87
M       206     301
M       213     372
M       321     255
M       319     99
M       221     404
M       439     311
M       440     167
M       205     228
M       127     150
M       484     158
M       420     224
M       422     269
M       396     81
M       130     84
M       292     472
M       172     350
M       125     385
M       222     299
M       140     42
M       398     213
M       298     190
M       24      90
M       209     81
M       319     336
M       232     155
M       494     4
M       379     269
M       273     276
M       350     255
M       360     142
M       79      384
M       493     205
M       121     67
M       4       113
M       461     254
M       326     259
M       444     202
M       202     6
M       284     21
M       342     368
#

AC output:

Code: Select all

T
J
L
R
J
L
W
P
Y
J
 30
Y
Y
L
J
Y
  9
 33
X
Y
R
L
Y
J
X
R
Y
X
Y
 33
  9
 11
Y
Y
L
L
W
Y
 33
B
W
Q
Y
  5
P
J
Y
Y
O
R
L
Y
U
J
  5
W
Y
 33
Y
Y
R
 11
Y
Y
 11
X
 30
Y
L
B
Y
Y
Y
L
 11
R
 36
Y
L
Y
Y
L
Y
L
Y
 33
Y
Y
Y
Y
 36
B
L
L
J
Y
J
 33
Y
Q

[happyson10]

got it? thanks

[lighted]

The problem statement says:
Coordinates will be given as pairs of integers in the range 0..499 and you can assume that all icons and regions lie wholly within the screen.

But the tests above contain bigger integers like 560. is judge contain such numbers?

[lighted]

I got acc. The statement really ambiguous. It must be clearly stated that if icon comes later and lies on existing region -> it will be invisible or obscured.
Judge don't contain integers greater 0..499.

[brianfry713]

I corrected the I/O in my previous post.