Page 1 of 1
638 - Finding Rectangles
Posted: Fri Jul 26, 2002 1:04 am
by 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?!
638 wa
Posted: Fri Nov 08, 2002 8:27 am
by 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]
Yes there is a trick
Posted: Sun Nov 10, 2002 7:30 pm
by 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
638 Why WA?
Posted: Mon Oct 11, 2004 5:13 pm
by 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
Posted: Mon Oct 11, 2004 7:25 pm
by Maddas
I found the mistake, I don't understand why it didn't work before but it works now.
Re: 638 why?
Posted: Fri Dec 02, 2005 2:35 am
by DongJoo Kim
Denis wrote: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.
Re: Yes there is a trick
Posted: Fri Dec 02, 2005 2:43 am
by DongJoo Kim
ec3_limz wrote: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.
Re: 638 why?
Posted: Thu May 11, 2006 7:25 am
by lyh91208
DongJoo Kim wrote:
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.
help
Posted: Tue Aug 14, 2007 1:04 pm
by 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.
Re: help
Posted: Tue Aug 14, 2007 7:59 pm
by Jan
rezaeeEE wrote: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.
Its a vaid input. but
its not valid, since the label 'B' appears before 'A'.
If your code gets wa then check it again carefully.
help
Posted: Tue Aug 14, 2007 10:54 pm
by 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.
Posted: Wed Aug 15, 2007 2:44 pm
by 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.
help
Posted: Wed Aug 15, 2007 4:50 pm
by rezaeeEE
very very silly mistake.
my program cout << endl 11 perline.
thanks mr jane.
i got accept.
Re: 638 - Finding Rectangles
Posted: Thu Nov 13, 2008 4:00 pm
by DD
In this problem, be aware that don't print a extra '\n' when the number of rectangles are times of 10.