585 - Triangles

[LTH]

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[110][220],s[110][220],max,lb,rb;
char read[300];
while(scanf("%ld",&num)!=EOF)
{
if(num==0)
{
break;
}
for(i=0;i<num;i++)
{
scanf("%s",&read);
for(j=0;j<strlen(read);j++)
{
if(read[j]=='#')
{
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);
}
}

[Adrian Kuegel]

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]

OH...I finally figure out your meaning...^^
I got Accepted... ^^
thank you very much^^

[tat tvam asi]

helo !

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

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 ?

thanks for advance
tat tvam asi

[junjieliang]

Code: Select all

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

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

[tat tvam asi]

thanks junjieliang !

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

bye
tat tvam asi

[Nick]

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.

Hope this can help you guys

[rodriwan]

isnt the area of triangle for == 4?

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

or is your output right?

[Nick]

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]

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

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]

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..

[CDiMa]

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]

Now I got AC!!
Thank you very much..~

[Ron]

Why im getting WA...Please help me....!!

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.

Thnx in advance..!!