638 - Finding Rectangles

[Denis]

In problem said: "Within each set, points labels occur in alphabetical order".
Code with sorting this labels gives AC, but without WA.

Maybe BUG or I something not understand?!

[lowai]

any trick there?

[cpp]
#include <fstream.h>

struct Point {
int x, y;
char label;
};

const int MAXSIZE = 26;
const int PERLINE = 10;

int main() {

int caseno = 0, nRect, nPoints, tl, tr, bl, br;

Point pt[MAXSIZE];

cin >> nPoints;
while (nPoints > 0) {
for(int i=0; i < nPoints; i++)
cin >> ws >> pt.label >> pt.x >> pt.y;

caseno++;

cout << "Point set " << caseno <<':';

nRect = 0;

for(tl = 0; tl < nPoints; tl++)
for(tr = 0; tr < nPoints; tr++)
if (pt[tr].y == pt[tl].y && pt[tr].x > pt[tl].x)
for(br = 0; br < nPoints; br++)
if (pt[tr].x == pt[br].x && pt[br].y < pt[tr].y)
for(bl = 0; bl < nPoints; bl++)
if (pt[bl].x == pt[tl].x && pt[bl].y == pt[br].y) {
if (nRect % PERLINE == 0) cout << endl;
nRect++;
cout << ' ' << pt[tl].label << pt[tr].label <<
pt[br].label << pt[bl].label;
}
if (nRect == 0) cout << " No rectangles";
cout << endl;

cin >> nPoints;
}
return 0;
}

[/cpp]

[ec3_limz]

Hi lowai,

I recently found out that there may be a trick in this problem. I cannot, however, confirm that what I say is correct.

The problem did NOT state that all rectangles must be parallel to the axes. This means that rectangles can be in any "direction", e.g. diamonds.

For example.

SAMPLE INPUT
4
A 0 1
B 1 0
C 2 3
D 3 2

SAMPLE OUTPUT
Point Set 1:
CDBA

[Maddas]

Hi, my program works fine for the sample input and produces correct output for many random input files I generated (I gave it to a friend who has a program that gives the right answer and his output was the same as my output)

Are there any really tricky test cases? Can points be on top of each other?

Does anybody have any input file to test with and output that I can compare with?

I really don't know where the problem is, any help greatly appreciated,

Maddas

[Maddas]

I found the mistake, I don't understand why it didn't work before but it works now.

[DongJoo Kim]

In problem said: "Within each set, points labels occur in alphabetical order".
Code with sorting this labels gives AC, but without WA.

Maybe BUG or I something not understand?!

You are right.

I finally got AC after I sorted the input. Thanx..

I think the description should be fixed.

[DongJoo Kim]

Hi lowai,

I recently found out that there may be a trick in this problem. I cannot, however, confirm that what I say is correct.

The problem did NOT state that all rectangles must be parallel to the axes. This means that rectangles can be in any "direction", e.g. diamonds.

For example.

SAMPLE INPUT
4
A 0 1
B 1 0
C 2 3
D 3 2

SAMPLE OUTPUT
Point Set 1:
CDBA

I think above explanation is FALSE.
I followed your explanation of rectangle. However, what I've got was 10+ WAs. After changing to normal rectangle( rectangle with parallel to X-axis or Y-Axis) I got AC.

In short, in this problem, side of rectangle is always parallel to the X-axis or Y-axis.

[lyh91208]

I finally got AC after I sorted the input. Thanx..

Sorry, but I don't understand what it means.

Can anyone explain it more?

Thanks.

[rezaeeEE]

i cnat understand this sentence:

"Within each set, points labels occur in alphabetical order"

can any body explain this with a example?

i get wa and i dont know which part of my program is wrong.

[Jan]

i cnat understand this sentence:

"Within each set, points labels occur in alphabetical order"

can any body explain this with a example?

i get wa and i dont know which part of my program is wrong.

The sentence means that the labels will be given in alphabetical order.

Code: Select all

3
A 1 1
B 2 1
C 3 1

Its a vaid input. but

Code: Select all

3
B 1 1
A 2 1
C 3 1

its not valid, since the label 'B' appears before 'A'.

If your code gets wa then check it again carefully.

[rezaeeEE]

thank u very much mr jan.

for this input:
4
B 1 1
A 0 0
C 1 0
D 0 1

the output must be : No rectangles ??

can u give me some tricky inputs.thanks.

[Jan]

As I said earlier the input is not valid. So, this type of inputs will not appear in the input file. Its tough to generate cases for this problem. However, you can post your code. Then it would be easier to find the error.

[rezaeeEE]

very very silly mistake.

my program cout << endl 11 perline.

thanks mr jane.
i got accept.

[DD]

In this problem, be aware that don't print a extra '\n' when the number of rectangles are times of 10.