1. 

/**
* FWP, Ausgewaehlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 585 Triangles
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=526
*
* @author Barny Porcio
* @version 1.0, 03/27/2010
*
* Method : -
* Status : Accepted
* Runtime: 0.208
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Triangles585{
//2D Array, 1.[]stellt die Zeile des Dreiecks dar, das 2.[] das Zeichen
//1.[n-1] ist die oberste reihe 2.[0] das linkeste element
static boolean[][] triangle;

/**Berechnet ausgehend von Zeile stufe und Spalte mittelposition
* das von diesem standpunkt aus groesste dreieck ohne luecke dazwischen
* @param up: gibt an ob nach oben oder unten gesucht werden soll
* @param stufe: von welcher stufe aus die berechnung starten soll
* @param mittelposition: von welchem Zeichen aus die berechnung starten soll
* @return: gibt die von diesem standpunkt aus groesste dreiecksflaeche zurueck
*/
static int calculate(boolean up, int stufe, int mittelposition){
if (up){
//geht je eine stufe bis zur maximalen stufe hoch
for(int i= stufe; i<triangle.length;++i){
//geht die spalten einer reihe entlang und schaut ob es eine luecke dazwischen gibt
for(int position = mittelposition-(i-stufe);position<=mittelposition+(i-stufe);++position){
if (!triangle[i][position])
return (i-stufe) * (i-stufe);
}
}
//wenn es bis nach oben durchging muss das groesste dreieck noch gesetzt werden, da es nicht aufgehalten wurde muss es bei der maximalen laenge triangle-lengt aufgehoert haben
return (triangle.length-stufe) * (triangle.length-stufe);
}
//das selbe nochmal wenn es nach unten kalkuliert werden soll
else {
for(int i= stufe; i>=0;--i){
for (int position = mittelposition - (stufe - i); position <= mittelposition + (stufe - i) ; ++position){
//System.out.println("position"+position);
if (!triangle[i][position])
return (stufe-i) * (stufe-i);
}
}
return stufe * stufe;
}
}

public static void main(String[] args) throws IOException, InterruptedException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//liesst die groesse des dreiecks ein
int size = Integer.parseInt(br.readLine());
int counter = 1;
while (size != 0){
int biggesttriangle = 0;
triangle = new boolean[size][size*2-1];
--size;
//uebertraegt das dreieck in das 2d array triangle
while (size >= 0){
String temp = br.readLine();
for(int i = triangle.length-1-size;i<triangle[0].length-(triangle.length-1-size);++i){
if (temp.charAt(i) == '-')
triangle[size][i] = true;
}
--size;

}


//geht das komplette dreieck durch und ueberprueft von bei jedem '-' mit der methode calculate
//das groest moegliche dreieck an der stelle und aendert biggesttriangle wenn noetig ab
for(int i = triangle.length-1;i >= 0;--i){
boolean status = false;
for(int i2 = (triangle.length-1)-i; i2 <= (triangle[0].length-1)-(triangle.length-1-i) ; ++i2){
status = !status;
if (triangle[i][i2]){
int newcalc = calculate(status, i, i2);
if (biggesttriangle < newcalc)
biggesttriangle = newcalc;
}
}
}
System.out.println("Triangle #"+counter+'\n'+"The largest triangle area is "+biggesttriangle+".\n");
++counter;
size=Integer.parseInt(br.readLine());
}
}
}

2.

/**
* FWP, Ausgewaehlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 585 Triangles
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=526
*
* @author Barny Porcio
* @version 1.0, 03/27/2010
*
* Method : -
* Status : Runtime Error - Threads
* Runtime: -
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Triangles585thread extends Thread{
//2D Array, 1.[]stellt die Zeile des Dreiecks dar, das 2.[] das Zeichen
//1.[n-1] ist die oberste reihe 2.[0] das linkeste element
static boolean[][] triangle;

//groesste Flaeche
static int biggesttri = 0;

//anzahl der momentan aktiven Threads
static int activethreads = 0;
boolean up;
int stufe;
int mittelposition;
public Triangles585thread(boolean up, int stufe, int mittelposition) {
// TODO Auto-generated constructor stub
this.up = up;
this.mittelposition = mittelposition;
this.stufe = stufe;
}

@Override
public void run() {

int temp = calculate(up, stufe, mittelposition) ;
synchronized (triangle) {
if (temp > biggesttri)
biggesttri = temp;
--activethreads;
triangle.notifyAll();
}

}

/**Berechnet ausgehend von Zeile stufe und Spalte mittelposition
* das von diesem standpunkt aus groesste dreieck ohne luecke dazwischen
* @param up: gibt an ob nach oben oder unten gesucht werden soll
* @param stufe: von welcher stufe aus die berechnung starten soll
* @param mittelposition: von welchem Zeichen aus die berechnung starten soll
* @return: gibt die von diesem standpunkt aus groesste dreiecksflaeche zurueck
*/
int calculate(boolean up, int stufe, int mittelposition){
if (up){
//geht je eine stufe bis zur maximalen stufe hoch
for(int i= stufe; i<triangle.length;++i){
//geht die spalten einer reihe entlang und schaut ob es eine luecke dazwischen gibt
for(int position = mittelposition-(i-stufe);position<=mittelposition+(i-stufe);++position){
if (!triangle[i][position])
return (i-stufe) * (i-stufe);
}
}
//wenn es bis nach oben durchging muss das groesste dreieck noch gesetzt werden, da es nicht aufgehalten wurde muss es bei der maximalen laenge triangle-lengt aufgehoert haben
return (triangle.length-stufe) * (triangle.length-stufe);
}
//das selbe nochmal wenn es nach unten kalkuliert werden soll
else {
for(int i= stufe; i>=0;--i){
for (int position = mittelposition - (stufe - i); position <= mittelposition + (stufe - i) ; ++position){
//System.out.println("position"+position);
if (!triangle[i][position])
return (stufe-i) * (stufe-i);
}
}
return stufe * stufe;
}
}

public static void main(String[] args) throws IOException, InterruptedException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//liesst die groesse des dreiecks ein
int size = Integer.parseInt(br.readLine());
int counter = 1;
while (size != 0){
triangle = new boolean[size][size*2-1];
--size;
//uebertraegt das dreieck in das 2d array triangle
while (size >= 0){
String temp = br.readLine();
for(int i = triangle.length-1-size;i<triangle[0].length-(triangle.length-1-size);++i){
if (temp.charAt(i) == '-')
triangle[size][i] = true;
}
--size;

}

//geht das komplette dreieck durch und ueberprueft bei jedem '-' ueber einen neuen Thread mit der methode calculate
//das groest moegliche dreieck an der stelle. Es können Maximal 3 Threads laufen
for(int i = triangle.length-1;i >= 0;--i){
boolean status = false;
for(int i2 = (triangle.length-1)-i; i2 <= (triangle[0].length-1)-(triangle.length-1-i) ; ++i2){
status = !status;
if (triangle[i][i2]){
synchronized (triangle) {
while(activethreads > 2)
triangle.wait();
++activethreads;
new Triangles585thread(status, i, i2).start();


}

}
}
}
//bevor die groesste <flaeche ausgegeben werden kann muessen erst alle Threads beendet sein.
synchronized (triangle) {
while(activethreads != 0)
triangle.wait();
}

System.out.println("Triangle #"+counter+'\n'+"The largest triangle area is "+biggesttri+".\n");
biggesttri = 0;
++counter;
size=Integer.parseInt(br.readLine());
}
}
}


3.

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Dynamic Programming
* Problem: 585 - Triangles
* Accepted: 0.284
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static boolean[][][] triangle;

private static int maxFound;
private static int height;
private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));



private static void parseTriangle() throws Exception
{
String input;
for(int h = height-1; h >= 0; h--)
{
input = reader.readLine().trim();
for(int x = 0; x < input.length(); x++)
if(input.charAt(x) == '-')
{
triangle[h][x][0] = true;
maxFound = 1;
}
}
}


private static void bottomUp()
{
// accumulate upside down triangles with size k (1,2,...)
for(int k = 1; k < height; k++)
for(int h = 0; h < height-k; h++)
for(int x = 0; x < h*2+1; x+=2)
if(triangle[h][x][k-1] &&
triangle[h+1][x][k-1] &&
triangle[h+1][x+2][k-1] &&
(k != 1 || triangle[h+1][x+1][k-1]))
{
if(k+1 > maxFound)
maxFound = k+1;
triangle[h][x][k] = true;
}

// accumulate upward triangles
for(int k = 1; k <= height/2-1; k++)
for(int h = height-1; h > k*2; h--)
for(int x = k*2+1; x < (h*2)-(k*2); x+=2)
if(triangle[h][x][k-1] &&
triangle[h-1][x][k-1] &&
triangle[h-1][x-2][k-1] &&
(k != 1 || triangle[h-1][x-1][k-1]))
{
if(k+1 > maxFound)
maxFound = k+1;
triangle[h][x][k] = true;
}
}



public static void main(String... args) throws Exception
{
int caseNumber = 1;

while(true)
{
height = Integer.parseInt(reader.readLine());
if( height == 0 )
break;

triangle = new boolean[height][height*2-1][height];
maxFound = 0;

parseTriangle();
bottomUp();

System.out.printf("Triangle #%d\n", caseNumber++);
System.out.printf("The largest triangle area is %d.\n\n", maxFound*maxFound);
}

}
}ge