209 - Triangular Vertices

[bobi1978]

There are two types of triangles:
--
\/

/\
--

Three types of parallelograms:
---
/ /
---

---
\ \
---

/\
/ \
\ /
\/

One type of hexagon:
---
/ \
\ /
---

It seems that there are no inputs of type :
--
/ /
\ \
--
because I got ACC WITH AND WITHOUT checking for this figure to be a hexagon.

[samueljj]

I've checked all the possible formations. But don't understand why still getiing WA? Can anybody provide some critical inputs

[Ivor]

how about
10 11 15
8 11 20
6 8 17

Ivor

[Charlla]

Hy!


Can anyone help me? I need some critical input examples for problem 209.

Thanks,

Charlla

[Unlimited]

Why does this code get WA?
My program analises: 2 different triangle types, 3 different paralelogram types; 1 hexagon type;
[cpp]
#include<stdio.h>
#include<iostream>
#include<sstream>

using namespace std;

struct Coord {
int x;
int y;
};

int triangle(Coord *p, long *d);
int parallelogram(Coord *p,long *d);
int hexagon(Coord *p,long *d);

int sort(int *p,int size) {
int i,j;
int k;
for(i=0;i<size-1;i++) {
if (p>p[i+1]) {
j=i+1;
while ((j>0) && (p[j-1]>p[j])) {
//cout << "j=" <<j << " ";
k=p[j-1];
p[j-1]=p[j];
p[j]=k;
j--;
}
}
}
return 0;
}

int readline(const char *str,int *p)
{
int i=0;
istringstream ist(str);
while (ist >> p) {
printf("%d ",p);
if (i<=6)
i++;
}
return i;
}

int main() {
int p[8]; //points;
int i,count;
char line[5000];
Coord c[6];
long d[6];
while (!cin.eof()) {
cin.getline(line,5000); //read 1 input line
count=readline(line,p);
if(count>6 || count<3 || count==5) {
printf("are not the vertices of an acceptable figure\n");
}
else {
sort(p,count);
d[0]=0;
//convert p to (x,y)
for(i=0;i<count;i++)
{
if (i>0)
d=d[i-1];
while((d+1)*(d+2)/2 < p) d++;
c.x=(d[i]+1)*(d[i]+2)/2-p[i];
c[i].y=d[i]-c[i].x;
}
switch(count) {
case 3:if (triangle(c,d))
printf("are the vertices of a triangle\n");
else printf("are not the vertices of an acceptable figure\n");
break;
case 4:if (parallelogram(c,d))
printf("are the vertices of a parallelogram\n");
else printf("are not the vertices of an acceptable figure\n");
break;
case 6:if (hexagon(c,d))
printf("are the vertices of a hexagon\n");
else printf("are not the vertices of an acceptable figure\n");
break;
}

}
}
return 0;
}

int triangle(Coord* p,long *d) {
if ((d[0]==d[1]) && (p[0].x!=p[1].x) &&
(p[0].x==p[2].x) && (p[1].y==p[2].y))
return 1;
else if ((p[1].x+p[1].y==p[2].x+p[2].y) && (p[1].x!=p[2].x) &&
(p[0].x==p[2].x) && (p[0].y==p[1].y))
return 1;
else return 0;
}
int parallelogram(Coord *p,long *d) {
if ((d[0]==d[1]) && (p[0].x!=p[1].x) &&
(d[2]==d[3]) && (p[2].x!=p[3].x) && (d[0]<d[2])) {
if ((p[0].y==p[2].y) && (p[1].y==p[3].y) && (p[0].x==p[3].x))
return 1;
else if ((p[0].x==p[2].x) && (p[1].x==p[3].x) && (p[1].y==p[2].y))
return 1;
else return 0;
}

if ((d[1]==d[2]) && (d[0]<d[1]) && (d[1]<d[3]) &&
(p[0].x==p[2].x) && (p[0].y==p[1].y) &&
(p[1].x==p[3].x) && (p[2].y==p[3].y))
return 1;
return 0;

}

int hexagon(Coord *p,long *d) {
if ((d[0]==d[1]) && (d[2]==d[3]) && (d[4]==d[5]) && (p[0].x!=p[1].x) &&
(p[0].y==p[2].y) && (p[1].y==p[4].y) && (p[3].y==p[5].y) &&
(p[0].x==p[5].x) && (p[1].x==p[3].x) && (p[2].x==p[4].x))
return 1;
else return 0;
}
[/cpp]

[raiku]

Hi!

I've got a question about problem 209. A polygon with side length 0 is permitted? I mean, is 1 1 1 a valid triangle?

I'm getting WA again and again and I don't know any other special case...

Thank you very much!!

Bernat

[junbin]

in case you don't realise.. there are:

2 types of triangles
3 types of parralleogram
1 type of hexagon

[GreenPenInc]

OK, I'm officially sick of reading in input whose end isn't signalled by a zero or something. Example: problem 209. I've had the logic down for a while now, and it runs like a dream on my own computer, but I alternate between RTE and TLE when I submit. What's a good way to handle cases where you keep on reading until EOF? I'd love to hear multiple people's thoughts on this. Thanks!

[shamim]

If you are using C/C++
Take the entire line of input into a char array, and then use
strtok().

[GreenPenInc]

Hmm... thanks, that's what I have been doing. I just hate doing it

What REALLY burns me up is the following. I've been writing a function to take a string and return an int. It all compiles fine on my machine. The following also compiles on Valladolid.

[cpp]
int make_int(string s)
{
int result = 0, i, temp;
for (i = 0; i < s.length(); i++)
{
//result = result * 10;
temp = s.at(i) - 48;
//result += temp;
//result = result + (s.at(i) - '0');
}
return result;

/*
for (int i = 0; i < s.length(); i++)
{
result *= 10;
result += (int)(s.at(i) - '0');
}
return result;
*/
}
[/cpp]

[cpp]
The following does NOT.int make_int(string s)
{
int result = 0, i, temp;
for (i = 0; i < s.length(); i++)
{
//result = result * 10;
temp = s.at(i) - 48;
result += temp;
//result = result + (s.at(i) - '0');
}
return result;

/*
for (int i = 0; i < s.length(); i++)
{
result *= 10;
result += (int)(s.at(i) - '0');
}
return result;
*/
}


[/cpp]

Now, why the hell would result += temp, when they're both integers, cause me to get TLE? I have isolated it (through scores of intentionally wrong submissions) to this very line of code. What the hell is going on?

[Krzysztof Duleba]

All my programs have the following shape:

[cpp]while(true){
Typename t;
if(cin >> t)break;
}[/cpp]
or
[cpp]while(true){
Typename t;
cin >> t;
if(t == EndOfInputCharacter)break;
}[/cpp]

It is also very easy to use scanf or fgets instead of cin here. In the first case, just look at the value returned by reading function (0 means EOF), in second - compare t with EndOfInputCharacter. So generally everything stays the same, and if the first input value is the number of cases, I simply ignore it.

[GreenPenInc]

Okay, after asking around in #c++ (and getting badgered for the bad habits I developed by doing competitions ) I found the following scheme. As always, it works great on my own comp, but I'm getting a SIGSEGV on the Online Judge. Help?!

[cpp]
int main()
{
int nums[6], length, i;
char * line;
string msg;
while (cin.getline(line, 256))
{
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]

[GreenPenInc]

FOR ANYONE WHO GOT AC

I ONLY need to see your INPUT. I have tried everything and am at the end of my rope. Please, just show me how to input using cin. Here's my main method. Works GREAT on my computer.

[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]

This gives me TLE on the Judge; it doesn't know when to stop seeking input. I have over 50 submissions trying to debug this. Just help me. Somebody. Please.

[Adrian Kuegel]

I am astonished that it works on your computer;

char * line;

This doesn't allocate any memory, so when you use
cin.getline(line,256);
where should the function getline write its result?

Just tried it on my computer, and it works, too. But I think that this is just luck, because line points to some address. Now if you write char *line = NULL you will see that it will not work.
So the thing you have to do is:
char line[258];

[CDiMa]

I am astonished that it works on your computer;

char * line;

This doesn't allocate any memory, so when you use
cin.getline(line,256);
where should the function getline write its result?

Just tried it on my computer, and it works, too. But I think that this is just luck, because line points to some address. Now if you write char *line = NULL you will see that it will not work.
So the thing you have to do is:
char line[258];

The online judge is very picky about memory addressing.
Most off-by-one errors I made got unnoticed when compiled locally but got caught by the OJ.
Basically this happens because SIGSEGV signals are generated when accessing memory outside the memory segment assigned to the process. If you access unallocated memory that happens to be within a segment owned by your program you don't get a sigfault.
To catch those nasty mistakes you need extra checking enabled.
You may want to use stackguard to catch that nasty bugs...

Ciao!!!

Claudio