1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming
* Contest, WS10/11
* Problem: 585 Triangles
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=526
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : Dynamic programming
* Status : Accepted
* Runtime: 0.276
*/

import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader inputReader = new BufferedReader(new InputStreamReader(System.in));

int lines = Integer.parseInt(inputReader.readLine());
String triangleLine;

boolean[][] triangleWhite;
int subline;
int orientation;
int x,y;
int size, maxsize;
boolean lineIsWhite;

int counter = 1;

while (lines != 0) {
triangleWhite = new boolean[lines][];

// Read the triangle
// Save it upside down
for (int i = lines; i > 0; i--) {
triangleLine = inputReader.readLine().trim();
triangleWhite[i-1] = new boolean[2*i - 1];
for (int j = 0; j < (2*i - 1); j++) {
triangleWhite[i-1][j] = triangleLine.charAt(j) == '-';
}
}

maxsize = 0;

// Walk through the triangle and consider every position as a peak
// Try a subtriangle from there
for (int line = 1; line <= lines; line ++) {
for (int pos = 1; pos <= 2*line - 1; pos++) {
if (triangleWhite[line-1][pos-1]) {
size = 1;
subline = 0;
if ((pos % 2) == 0) {
// Even position, which means the subtriangle must go up
orientation = -1;
} else {
// Odd position, go down
orientation = 1;
}
while(true) {
// Scan next line
subline ++;
lineIsWhite = true;
for (int subpos = 0; subpos < 2*subline + 1; subpos++) {
y = line + (orientation*subline);
// Because our triangle is left justified we don't need to go to the left when going up
// But we need to go to the left double the amount when going down
x = subpos + pos;
if (orientation == -1) {
x -= 2*subline;
}
if ((y < 1) || (y > lines)) {
lineIsWhite = false;
break;
}
if ((x < 1) || (x > 2*y - 1)) {
lineIsWhite = false;
break;
}
if (!triangleWhite[y - 1][x - 1]) {
lineIsWhite = false;
break;
}
}
if (lineIsWhite) {
size += 2*subline + 1;
} else {
break;
}
}
maxsize = Math.max(size, maxsize);
}
}
}

System.out.printf("Triangle #%d\nThe largest triangle area is %d.\n\n", counter, maxsize);

lines = Integer.parseInt(inputReader.readLine());
counter++;
}
}

}



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 : 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());
}
}
}

3.

/**
* 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());
}
}
}


4.

/**
* 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