## 585 - Triangles

Moderator: Board moderators

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:
er..i don't know why i get wrong answer..
Does triangles can be counted in other direction ?
i have tested lots of situation but still cant find the fault....
The following is my code(i use Dynamic Programming):

#include <stdio.h>
#include <string.h>
void main()
{
long i,j,k,t,tmp,tmpx,num,cnt=0,sum,n,s,max,lb,rb;
while(scanf("%ld",&num)!=EOF)
{
if(num==0)
{
break;
}
for(i=0;i<num;i++)
{
{
{
n[j]=1;
}
else
{
n[j]=0;
}
}
}
for(i=0;i<num;i++)
{
sum=0;
for(j=0;j<(num-i)*2-1;j++)
{
sum+=n[j];
s[j]=sum;
}
}
max=0;
for(i=0;i<num;i++)
{
for(j=0;j<2*(num-i)-1;j++)
{
rb=-2;
sum=0;
for(k=0;k<num-i;k++)
{
rb+=2;
if(j>=2*(num-i-k)-1||j-rb<0)
{
break;
}
if(j-rb-1>=0)
{
sum=sum+s[i+k][j]-s[i+k][j-rb-1];
}
else
{
sum=sum+s[i+k][j];
}
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
}
}
for(i=0;i<num;i++)
{
sum=0;
for(k=0;k<=i;k++)
{
sum=sum+s[i-k][2*k];
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
for(j=1;j<2*(num-i)-1;j++)
{
sum=0;
for(k=0;k<=i;k++)
{
sum=sum+s[i-k][j+2*k]-s[i-k][j-1];
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
}
}
cnt++;
if(cnt>1)
{
printf("n");
}
printf("Triangle #%ldn",cnt);
printf("The largest triangle area is %ld.n",max);
}
}

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Try this input:
5
####-####
b##---##
bb#####
bbb###
bbbb#
0
(b = blank, in the second line three '-')
Output:
Triangle #1
The largest triangle area is 1.
On the first glance this seems to be false.
But look at the picture and you will understand.

<font size=-1>[ This Message was edited by: Adrian Kuegel on 2002-02-08 10:22 ]</font>

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:
OH...I finally figure out your meaning...^^
I got Accepted... ^^
thank you very much^^

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

### 585 ( triangles )

helo !

i tried to solve this ( 585 )
problem , but got wa .
could you tell me the right
( ie. produced by ac - ed prog )

5
#########
#--#--#
#---#
#-#
#
6
###########
#---#---#
#-----#
#---#
#-#
#
7
#############
#----#----#
#---#---#
#-----#
#---#
#-#
#
0

( sorry for the missing leading spaces )
my "solution" produces :

Triangle #1
The largest triangle area is 4.

Triangle #2
The largest triangle area is 9.

Triangle #3
The largest triangle area is 9.

i found on the web an official
solution written by Matthias Ruhl ,
send it to uva and got ac. but Ruhl's
solution produces :

Triangle #1
The largest triangle area is 1.

Triangle #2
The largest triangle area is 4.

Triangle #3
The largest triangle area is 4.

for the input above .
who has right ?

tat tvam asi

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Code: Select all

``````5
#########
#---###
#-###
###
#
``````
The output is NOT 4, but 1. Does your program work for this?

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
thanks junjieliang !

i misunderstood the
problem . i took care
of triangles which are
not triangles ...

bye
tat tvam asi

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### 585 why sometimes u got Wrong Answer.......

Hi everyone
sometimes when you've done exactly what the problem wants.......guess what ....WA.....
This is a funny experience of mine with prob 585
where i've got all test input case correctly outputed

9
#################
###############
#############
###########
#########
#######
#####
###
#
5
#--------
-------
-#---
-#-
-
4
#-#-#--
-----
---
-

5
#########
#---###
#-###
###
#

5
####-####
##---##
#####
###
#

0

Output is
Triangle #1
The largest triangle area is 0

Triangle #2
The largest triangle area is 16

Triangle #3
The largest triangle area is 9

Triangle #4
The largest triangle area is 1

Triangle #5
The largest triangle area is 1
The numbers are all correct.....but WA!!!!
Just because i forgot to put '.' (dot) after each numbers in the output

what i'm saying is that, sometimes people get wreckless or a bit careless.
So...if you got WA all the time doesn't mean that you're wrong..but maybe you're just forgetting something really small.

rodriwan
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

### triangle 4

isnt the area of triangle for == 4?

5
#########
#---###
#-###
###
#

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am
yes the output is correct.

if you draw the upside down pyramid, you'll know that the 4 triangle holes will not combine into one large triangle..so the largest would be only 1

any two triangle connected stands in opposite positions

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

### 585 carelessness makes WA

[cpp]const int MAX = 1024;
char triangle[MAX][MAX];[/cpp]

if MAX = 105

you will won't get RE but WA

it's difficult to find such stupid bug

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
My programs solves the inputs from all posts on this problem.
Could anybody post more inputs/outputs or look at my code?
[cpp]#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

vector < string > data;
string s;
long n, ans;

inline bool good(const long &i, const long &j){
return i > -1 && j > -1 && i < (long)data.size() &&
j < (long)data.size() && data[j] == '-';
}

int main(){

// ifstream cin("in.txt");
long t = 1;

while(cin >> n && n && getline(cin, s)){
ans = 0;

data.resize(n);

for(long i = 0; i < n; i++){
getline(cin, data);
data.resize(2*n + 10, ' ');
}

for(long i = 0; i < n; i++)
for(long j = 0; j < 2*n + 10; j++)
if(data[j] == '-'){
ans >?= 1;

if((i + j)%2){
for(long ii = 1; good(ii + i, j - ii); ii++)
for(long jj = j - ii; jj <= j + ii && good(ii + i, jj); jj++)
if(jj == j + ii) ans >?= ii + 1;
}else{
for(long ii = -1; good(ii + i, j + ii); ii--)
for(long jj = j + ii; jj <= j - ii && good(ii + i, jj); jj++)
if(jj == j - ii) ans >?= -ii + 1;
}

}

cout << "Triangle #" << t++ << endl;
cout << "The largest triangle area is " << ans*ans << ".\n\n";

}

return 0;
}[/cpp]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 585 - Triangles

probably i didn't get the problem correctly

#########
#---###
#-###
###
#

i checked some articles here..
but i still don't know why the answer for that case is not 4 but 1..
Last edited by helloneo on Fri Jun 08, 2007 6:04 am, edited 1 time in total.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 585 Triangles.. WA..

helloneo wrote:probably i didn't get the problem correctly

#########
#---###
#-###
###
#

i checked some articles here..
but i still don't know why the answer for that case is not 4 but 1..
I'm not experienced in ASCII art but this should show why the answer is 1...

Code: Select all

``````-------------------
\#/#\#/#\#/#\#/#\#/
-----------------
\#/ \ / \#/#\#/
-------------
\#/ \#/#\#/
---------
\#/#\#/
-----
\#/
-
``````
Ciao!!!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Now I got AC!!
Thank you very much..~

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### Re: 585 - Triangles

Code: Select all

``got AC``

Input :

Code: Select all

``````1
-
1
#
2
#--
#
3
-----
--#
-
3
-#-#-
---
#
4
###-###
#---#
###
#
4
---#--#
#-##-
#--
-
4
#-#-#--
#---#
##-
-
0
``````
My program gives..

Output :

Code: Select all

``````Triangle #1
The largest triangle area is 1.

Triangle #2
The largest triangle area is 0.

Triangle #3
The largest triangle area is 1.

Triangle #4
The largest triangle area is 4.

Triangle #5
The largest triangle area is 1.

Triangle #6
The largest triangle area is 4.

Triangle #7
The largest triangle area is 1.

Triangle #8
The largest triangle area is 4.

``````