OJ Board

i think i have solved 142 - but i still get WA.

can someone provide me with additional input/output data to help me track the bug(s) down? or some ideas of extreme cases?

Thanks

Mouquiette

??

when program NO.142,i used getch() fuction to judge the first letter to know whether the input is a I(icon) or a R(Region) or a M.
/*
while(1)
{
kind=getch();
if (kind=='I') scanf("%d %d",a,b);
if (kind=='R') scanf("%d %d %d %d",a,b);
if (kind=='#') break;
}
*/

but getch() is Borland compiler specific function (non ISO). conio.h header is also present only in Borland products, thus judge system (which is GNU GCC suite) does not have them.

i can't replace the fuction getch() with scanf(),cin.get(),getchar(),because those fuction will either treat 'enter' as character or wait untill 'enter'.So i wanna know is there any fuction exactly like getch() or some syntax that can solve that problem.Please tell me if u know. Thank u!

[c]char c;
scanf (" %c", &c);
[/c]
The space after the first quotation mark takes care of any whitespace, including any unwanted newlines.

You can also use:
Your expected character will be in str[0].

-turuthok-

but those number after the first character can not be ignore,they are useful.have u read the No.142 problem?i should judge which scanf() to use
( scanf(%d %d,&a,&b) or scanf(%d %d %d %d,&a,&b,&c,&d) )
through the first character

That should be simple, ... first, you can scanf("%s") ... and then based on the first character of s, you do another scanf() ... right ???
-turuthok-

part of 142 code

turuthok wrote:That should be simple, ... first, you can scanf("%s") ... and then based on the first character of s, you do another scanf() ... right ???

Code: Select all

scanf("%s", s);

switch(s[0]) {
    case '#':
        return 0;
    case 'I':
        scanf("%d %d", &a, &b);
        /* continue your code ... */

    case 'R':
        scanf("%d %d %d %d", &a, &b, &c, &d);
        /* continue your code */

    case 'M':
        scanf("%d %d", &a, &b);
        /* continue your code */
}

-turuthok-

but the I/R/M and the var a/b should input in one line

Hmm, ... scanf("%s") won't necessarily read until the end of line ... it would read the first token it sees ... it will stop scanning when it sees a whitespace.

Try it out ... I'm sure you'll get it.

-turuthok-

turuthok,thank u

Morning, no problem at all ...

Oh yes, was that your real judge-id in the posted-code above, ... make sure you don't disclose it ... someone might use it for nasty purpose.

-turuthok-

oh,yes.thank u for your reminding!i was so carefulless!

I solved this problem easily.

But, judge server judged Wrong Answer.

I can't find my mistake...ToT

Give me correct input and output set.

Help me......ToT~~~~


[cpp]
#include <stdio.h>

typedef struct _POINT {
int x;
int y;
bool hidden;
} POINT;

typedef struct _RECT {
int left;
int top;
int right;
int bottom;
} RECT;

void remove_hidden_icon(RECT *prect, int rects, POINT *picon, int icons);
bool find_rect(RECT *prect, int rects, POINT click);
void find_icon(POINT *picon, int icons, POINT click);
bool inner_rect(RECT rect, POINT point);
int square(int a);

int main()
{
POINT mouse, icon[50];
RECT rect[25];
int icon_count = 0, rect_count = 0;
char line[255];
bool start_click = false;

while (gets(line) != NULL) {
if (line[0] == '#') { // end condition
icon_count = rect_count = 0;
start_click = false;
} else if (line[0] == 'I') { // Icon input
sscanf(&line[1], "%d %d", &icon[icon_count].x, &icon[icon_count].y);
icon[icon_count].hidden = false;
icon_count++;
} else if (line[0] == 'R') { // Rect input
sscanf(&line[1], "%d %d %d %d", &rect[rect_count].left, &rect[rect_count].top,
&rect[rect_count].right, &rect[rect_count].bottom);
rect_count++;
} else if (line[0] == 'M') { // Mouse input
if (start_click == false) {
remove_hidden_icon(rect, rect_count, icon, icon_count);
start_click = true;
}
sscanf(&line[1], "%d %d", &mouse.x, &mouse.y);

if (!find_rect(rect, rect_count, mouse))
find_icon(icon, icon_count, mouse);
}
}

return 0;
}

void remove_hidden_icon(RECT *prect, int rects, POINT *picon, int icons)
{
for (int i = 0; i < icons; i++)
for (int j = 0; j < rects; j++) {
if (inner_rect(prect[j], picon)) {
picon.hidden = true;
break;
}
}
}

// find clicked rectangle
bool find_rect(RECT *prect, int rects, POINT click)
{
for (int i = rects - 1; i >= 0; i--)
if (inner_rect(prect, click)) {
printf("%c\n", (char)(i + 65));
return true;
}
return false;
}

// find the closest icon that clicked
void find_icon(POINT *picon, int icons, POINT click)
{
int closest = 250000;
int length[50], i;
for (i = 0; i < icons; i++)
if (picon.hidden == false) {
length = square(picon.x - click.x) + square(picon.y - click.y);
if (closest > length)
closest = length;
} else
length = -1;

for (i = 0; i < icons; i++)
if (closest == length[i])
printf("%3c", (char)(i + 49));
printf("\n");
}

bool inner_rect(RECT rect, POINT point)
{
if (rect.left <= point.x && rect.right >= point.x &&
rect.top <= point.y && rect.bottom >= point.y)
return true;
return false;
}

int square(int a)
{
return a * a;
}[/cpp]

Hmmm... I checked your code quickly, and it looks very similar to my AC program (we do the same operations). I don't know why your algorithm fails.

Here is my code. You can check more thoroughly where our programs differ.
[cpp]// @JUDGE_ID: 33444KK 142 C++
//
// 142_MouseClicks: Determine what region or icon is selected by a mouse click
//

#include <cstdio>

// The base types
#ifdef WIN32
typedef __int8 int8;
typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64;
typedef unsigned __int8 uint8;
typedef unsigned __int16 uint16;
typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;
#else
typedef char int8;
typedef short int16;
typedef long int32;
typedef long long int int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef unsigned long long int uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj) { if(pObj) { delete pObj; pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// The system's limits
#define MAX_ICONS 50
#define MAX_RECTS 25
#define MAX_COORD 500
#define MAX_DIST MAX_COORD * MAX_COORD

// An icon
struct ICON
{
uint16 u16X; // The x-coordinate
uint16 u16Y; // The y-coordinate
bool bVisible; // Is the icon visible?
};

// A rectangle
struct RECT
{
uint16 u16Left;
uint16 u16Top;
uint16 u16Right;
uint16 u16Bottom;
};

// Function prototypes
void FindClosestIcons(uint16 u16X, uint16 u16Y);
bool PointInRect(const RECT *pRect, uint16 u16X, uint16 u16Y);

// Global variables
ICON g_pIcons[MAX_ICONS]; // The positions of the icons
RECT g_pRects[MAX_RECTS]; // The positions of the rectangle
uint8 g_u8TotIcons, // The total amount of icons
g_u8TotRects; // The total amount of rectangles


//----------------------------------------------------------------
// F U N C T I O N S
//----------------------------------------------------------------


// This function is the entrance of the app
int main()
{
int8 pi8Type[8];

// Initially, we don't have any icons or rectangles
g_u8TotIcons = g_u8TotRects = 0;

// Get the next input
while(scanf("%s", pi8Type) == 1)
{
// What kind of input do we have?
if(pi8Type[0] == 'I')
{
// Add the icon
scanf("%hu %hu", &g_pIcons[g_u8TotIcons].u16X,
&g_pIcons[g_u8TotIcons].u16Y);
g_pIcons[g_u8TotIcons].bVisible = true;
g_u8TotIcons++;
}
else if(pi8Type[0] == 'R')
{
// Add the rectangle
scanf("%hu %hu %hu %hu", &g_pRects[g_u8TotRects].u16Left,
&g_pRects[g_u8TotRects].u16Top,
&g_pRects[g_u8TotRects].u16Right,
&g_pRects[g_u8TotRects].u16Bottom);
g_u8TotRects++;
}
else break;
}

// Check the visibility of the icons
for(uint8 u8Icon=0;u8Icon<g_u8TotIcons;u8Icon++)
{
// Check whether the icon is obscured by any of the rectangles
for(uint8 u8Rect=0;u8Rect<g_u8TotRects;u8Rect++)
{
// Is our icon obscured by the rectangle?
if(PointInRect(&g_pRects[u8Rect], g_pIcons[u8Icon].u16X, g_pIcons[u8Icon].u16Y))
{
// The icon isn't visible
g_pIcons[u8Icon].bVisible = false;
break;
}
}
}

// Continue while we have mouse clicks
while(pi8Type[0] == 'M')
{
uint16 u16X, u16Y;

// Get the mouse click
if(scanf("%hu %hu", &u16X, &u16Y) == 2)
{
bool bPointInRect = false;

// Is the mouse click in a rectangle?
for(int8 i8Rect=g_u8TotRects-1;i8Rect>=0;i8Rect--)
{
// Does the point lie in the rectangle?
if(bPointInRect = PointInRect(&g_pRects[i8Rect], u16X, u16Y))
{
// The point lies in the rectangle
printf("%c\n", 'A' + i8Rect);
break;
}
}

// Wasn't the mouse click in a rectangle?
if(!bPointInRect)
{
// Check which icon(s) is/are closest to the mouse click
FindClosestIcons(u16X, u16Y);
}
}

// Get the next input
if(scanf("%s", pi8Type) != 1)
pi8Type[0] = '\0';
}

return 0;
}


//----------------------------------------------------------------


// This function gets the icon(s) closest to the point
void FindClosestIcons(uint16 u16X, uint16 u16Y)
{
uint32 pu32Dist[MAX_ICONS], u32MinDist;

// Set the initial shortest distance
u32MinDist = MAX_DIST + 1;

// Get the distances to all the icons
for(uint8 u8Icon=0;u8Icon<g_u8TotIcons;u8Icon++)
{
// Is the icon visible?
if(g_pIcons[u8Icon].bVisible)
{
int32 i32Dx, i32Dy;

// Get the distance to the icon
i32Dx = g_pIcons[u8Icon].u16X - u16X;
i32Dy = g_pIcons[u8Icon].u16Y - u16Y;
pu32Dist[u8Icon] = i32Dx * i32Dx + i32Dy * i32Dy;

// Do we have a new shortest distance?
if(pu32Dist[u8Icon] < u32MinDist)
u32MinDist = pu32Dist[u8Icon];
}
else
pu32Dist[u8Icon] = MAX_DIST + 1;
}

// Show the icons with the shortest distance
for(uint8 u8Icon=0;u8Icon<g_u8TotIcons;u8Icon++)
{
// Show the icon nr
if(pu32Dist[u8Icon] == u32MinDist)
printf("%3u", u8Icon + 1);
}

// End the line
printf("\n");
}


//----------------------------------------------------------------


// This function checks whether a point lies in a rectangles
bool PointInRect(const RECT *pRect, uint16 u16X, uint16 u16Y)
{
// Does the point lie in the rectangle?
return u16X >= pRect->u16Left &&
u16X <= pRect->u16Right &&
u16Y >= pRect->u16Top &&
u16Y <= pRect->u16Bottom;
}[/cpp]