209 - Triangular Vertices

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post by bobi1978 » Tue Jul 29, 2003 8:36 am

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
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

Post by samueljj » Sun Aug 03, 2003 6:22 pm

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

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Aug 03, 2003 7:03 pm

how about
10 11 15
8 11 20
6 8 17

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

Problem 209 - Input Examples

Post by Charlla » Sat Dec 13, 2003 5:46 am

Hy!


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

Thanks,

Charlla

Unlimited
New poster
Posts: 1
Joined: Fri Mar 19, 2004 10:54 pm

209 WA

Post by Unlimited » Sat Mar 20, 2004 3:31 pm

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
New poster
Posts: 2
Joined: Sun Sep 14, 2003 5:29 pm
Location: Spain

209 - Triangular Vertices

Post by raiku » Tue Apr 20, 2004 4:40 am

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Apr 20, 2004 10:07 am

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

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

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

reading input whose end is not signalled

Post by GreenPenInc » Mon May 10, 2004 5:07 am

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!
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon May 10, 2004 6:53 am

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

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Mon May 10, 2004 1:58 pm

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?
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon May 10, 2004 2:14 pm

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.

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Tue May 11, 2004 4:39 am

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]
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Tue May 11, 2004 6:34 am

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.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue May 11, 2004 9:35 am

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue May 11, 2004 12:01 pm

Adrian Kuegel wrote: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

Post Reply

Return to “Volume 2 (200-299)”