209 - Triangular Vertices

[GreenPenInc]

I'd noticed and caught that by the time I went to bed last night, and changed it to char[256]. So I traded my RTEs for TLEs. Here's my present code.

[cpp]


int main()
{
int nums[6], length, i;
char line[257];
string msg;
while (!cin.getline(line, 256).eof())
{
length = 0;
istringstream iss(line);
while (iss >> nums[length++]);
length--;
msg = "are not the vertices of an acceptable figure";
switch(length)
{
case 3:
if (check_triangle(nums))
msg = "are the vertices of a triangle";
break;
case 4:
if (check_parallelogram(nums))
msg = "are the vertices of a parallelogram";
break;
case 6:
if (check_hexagon(nums))
msg = "are the vertices of a hexagon";
break;
}
for (i = 0; i < length; i++)
cout << nums << " ";
cout << msg << endl;
}

return 0;
}


[/cpp]

So, what is this stackguard which could save me so much grief, and how do I use it? By all means, if I can make my compiler more fussy locally for the contest problems, I'd be happy to do it.

[GreenPenInc]

Oh, and to clarify: the problem I'm now having is that whlie(!cin.getline(line, 256).eof()) doesn't seem to be triggering. In other words, the above statement hangs at the end of the file, waiting for more input from standard input.

[Krzysztof Duleba]

Use instead:
[cpp]while(true){
getline(cin, aString);
if(! cin)break;
}[/cpp]

[GreenPenInc]

Just tried it, thanks. Time Limit Exceeded: it still hangs!

This really shouldn't be that difficult. Anyone who got AC on this problem, can I see your input code?

[Adrian Kuegel]

Time Limit Exceeded does not always mean, your program hangs.
How do you check for triangle etc. ? Perhaps your program is just not efficient enough.
This is my reading part of the program:
string zeile;
while(getline(cin,zeile)) {
cout<<zeile;
istrstream lstr(zeile.c_str());
while(lstr>>d.val) {
// do something with value
}
// calculate answer
}

[GreenPenInc]

Here is my reason for thinking it hangs on the input. I used many of my incorrect submissions to break out of the loop after a certain number of iterations. When it's around 7700 or less, it returns WA in under a second. But over 7800, it hangs. Either there is some test input which it can't handle, or it's the end of input and it's hanging.

Here is my complete code.

[cpp]
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cmath>
#include <sstream>

using namespace std;

/* insertion sort */
int * sort(int * nums, int length)
{
int * iResult = new int[length];
int i, j, best;
for (i = 0; i < length; i++)
iResult = nums;
for (i = 1; i < length; i++)
{
best = iResult;
for (j = i - 1; j >= 0; j--)
{
if (iResult[j] <= best)
break;
iResult[j + 1] = iResult[j];
}
iResult[j + 1] = best;
}
return iResult;
}

/* returns the row number of a coordinate */
int row(int coord)
{
return (int)ceil(sqrt(2*coord + 0.25) - 0.5);
}

/* number of coord's left child is coord + length of the row it's on */
int left_child(int coord)
{
return coord + row(coord);
}

/* right child is one greater than left child */
int right_child(int coord)
{
return coord + row(coord) + 1;
}

/* distance along a down-left edge, -1 if it's not aligned */
int left_distance(int c1, int c2)
{
int length = 0, child = c1;
while (child < c2)
{
length++;
child = left_child(child);
}
if (child > c2) length = -1;
return length;
}

/* distance along a down-right edge, -1 if it's not aligned */
int right_distance(int c1, int c2)
{
int length = 0, child = c1;
while (child < c2)
{
length++;
child = right_child(child);
}
if (child > c2) length = -1;
return length;
}

/* straight-across distance, -1 if on different rows */
int horiz_distance(int c1, int c2)
{
if (row(c1) != row(c2)) return -1;
return abs(c1 - c2);
}

/* checks for triangle (can point up or down) */
bool check_triangle(int * num)
{
int * sorted = sort(num, 3);
bool bResult = false;
int length = right_distance(sorted[0], sorted[2]);
if (length > 0 && (horiz_distance(sorted[0], sorted[1]) == length || horiz_distance(sorted[1], sorted[2]) == length))
bResult = true;
delete [] sorted;
return bResult;
}

/* checks for parallelogram (diamond shape) */
bool check_parallelogram_a(int * num)
{
bool bResult = false;
int length = left_distance(num[0], num[1]);
if (length > 0 && right_distance(num[0], num[2]) == length && right_distance(num[1], num[3]) == length)
bResult = true;
return bResult;
}

/* checks for parallelogram (horizontal top & bottom, left or right slant) */
bool check_parallelogram_b(int * num)
{
bool bResult = false;
int length = horiz_distance(num[0], num[1]);
if (length > 0 && horiz_distance(num[2], num[3]) == length && (right_distance(num[1], num[3]) == length || left_distance(num[1], num[3]) == length))
bResult = true;
return bResult;
}

/* checks the 2 types of parallelogram */
bool check_parallelogram(int * num)
{
int * sorted = sort(num, 4);
bool bResult = check_parallelogram_a(sorted) || check_parallelogram_b(sorted);
delete [] sorted;
return bResult;
}

/* checks for a hexagon */
bool check_hexagon(int * num)
{
int * sorted = sort(num, 6);
bool bResult = false;
int length = horiz_distance(sorted[0], sorted[1]);
if (length > 0 && right_distance(sorted[1], sorted[3]) == length
&& right_distance(sorted[2], sorted[4]) == length
&& left_distance(sorted[0], sorted[2]) == length
&& left_distance(sorted[3], sorted[5]) == length)
bResult = true;
delete [] sorted;
return bResult;
}

int main()
{
int nums[6], length, i;
char line[257];
string msg, lin;
//while (!cin.getline(line, 256).eof())
while (getline(cin, lin))
{
length = 0;
istringstream iss(lin.c_str());
while (iss >> nums[length++]);
length--;
msg = "are not the vertices of an acceptable figure";
switch(length)
{
case 3:
if (check_triangle(nums))
msg = "are the vertices of a triangle";
break;
case 4:
if (check_parallelogram(nums))
msg = "are the vertices of a parallelogram";
break;
case 6:
if (check_hexagon(nums))
msg = "are the vertices of a hexagon";
break;
}
for (i = 0; i < length; i++)
cout << nums << " ";
cout << msg << endl;
}
return 0;
}
[/cpp]

[Adrian Kuegel]

Your mistake is here:
int row(int coord)
{
return (int)ceil(sqrt(2*coord + 0.25) - 0.5);
}
if coord = 1, your result as double value is perhaps something like 0.999999999999999
so you would return 0;
in this case you have endless loops in your left_distance or right_distance function. I think that child should change its value in each execution of the while loop. So you could check if this is always the case (I think not).
use instead:
int row(int coord)
{
return (int)ceil(sqrt(2*coord + 0.25) - 0.5 + 1e-9);
}

[GreenPenInc]

ceil rounds up. And, it works for 1 2 3 (and all given test data).

[Adrian Kuegel]

Well, my fault;
anyway, I think that your problem is definitely not in the input reading part.

[GreenPenInc]

Thanks so much everyone for all your help! I finally got AC!

Adrian showed me in a PM a very useful technique for checking your assumptions. You do
[cpp]
#include <assert.h>
[/cpp]
and then you use it by saying
[cpp]
assert(boolean_condition)
[/cpp]

Using the above method, I discovered that the judge uses some input which is less than or equal to 0. Simply returning false when such a coordinate was encountered gave me the AC which I honestly deserved about 50 submissions ago But I've learned a number of very valuable lessons here and to me, that's worth 60 or so wrong submissions. Come November I'll be that much better prepared.

Thanks again!

[GreenPenInc]

The problem description says that the integers are from 1 to 32767. However, in the judge's input, there are some integers that are <= 0. You should deal with these accordingly (return false, since they're invalid coordinates). This might cause all kinds of weird bugs. Beware!

[marian]

This problem (or at least it's input) is crap. You are right, there are integers <=0, but you should not always return false. It's weird, but I think you should return
0 1 2 are the vertices of a triangle
0 1 2 3 are the vertices of a parallelogram
-1 1 4 6 are the vertices of a parallelogram
At least, sample solution for this problem, I found on web, returns these results. So if your solution doesn't work exactly the same as this sample solution, I think you hardly get accepted.

Could somebody fix input for this problem? Adrian?

Marian

[Ryan Pai]

I typically use code that looks like this:

[cpp]
string s;
while(getline(cin,s)){
//... stuff
}
[/cpp]

[GreenPenInc]

Thanks. I should have mentioned that I had solved this problem a little while ago now, but I appreciate your input and came up with a very similar scheme.

[GreenPenInc]

Good news: the input has been fixed!