Betrachte ein Polygon $P$ mit waagerechten und senkrechten Kanten und $N$ Eckpunkten. Die Kanten dürfen sich nur an ihren Endpunkten treffen, und an jedem Eckpunkt treffen genau zwei Kantenenden aufeinander. Bewegt man sich gegen den Uhrzeigersinn entlang der Kanten von $P$, biegt man an jedem Eckpunkt nach links oder rechts ab. Ein Linksabbiegen wird mit $L$, ein Rechtsabbiegen mit $R$ bezeichnet. Somit beschreibt eine Zeichenkette aus $L$ und $R$ das Polygon. Das Polygon in Abbildung 1 wird beispielsweise beschrieben durch

$LLRLLRRLLRLLRLLRRLLR$

Bei der Darstellung eines Polygons durch eine Zeichenkette beginnt man immer am oberen Endpunkt seiner am weitesten links liegenden Kante. Dieses Zeichen ist immer $L$.

Abbildungen 1 und 2

Ein durch die gegebene Zeichenkette beschriebenes Polygon muss folgende Bedingung erfüllen: Für jede senkrechte Gerade $V$ gibt es höchstens zwei Schnittpunkte von $V$ mit den Innenbereichen der waagerechten Polygonkanten (ohne ihre Endpunkte).

Sei $B(P)$ für ein Polygon $P$ das kleinste Rechteck mit waagerechten und senkrechten Seiten, das $P$ enthält. Es wird durch die senkrechten und waagerechten Geraden bestimmt, die mit den am weitesten links, rechts, oben und unten liegenden Kanten von $P$ zusammenfallen (Abbildung 2).

Gegeben ist eine Zeichenkette der Länge $N$ aus $L$ und $R$. Zeichne ein dadurch beschriebenes Polygon $P$, das die obige Bedingung erfüllt. Jede Kantenlänge von $P$ muss ganzzahlig sein. Schreibe ein Programm, das die Fläche von $B(P)$ minimiert und diesen Minimalwert ausgibt.

Du musst die folgende Funktion für das Bewertungsprogramm implementieren.

int polygon(string S);

Die Funktion erhält eine Zeichenkette $S$ der Länge $N$, deren Zeichen $L$ oder $R$ sind. Finde unter den durch $S$ beschriebenen Polygonen $P$ eines mit minimaler Fläche von $B(P)$ und gib diese Fläche zurück.

Implementierungsdetails

Reiche genau eine Datei namens polygon.c oder polygon.cpp ein. Sie muss die folgende Funktion implementieren.

int polygon(string S);

Die Funktion muss wie oben beschrieben arbeiten. Weitere Funktionen für den internen Gebrauch sind erlaubt. Der eingereichte Code darf keine Ein-/Ausgabe ausführen und nicht auf andere Dateien zugreifen.

Beispiel-Bewertungsprogramm

Das bereitgestellte Bewertungsprogramm liest die Eingabe im folgenden Format.

• Zeile 1: $N$ (die Länge der Zeichenkette).

• Zeile 2: eine Zeichenkette $c_1c_2\cdots c_N$ der Länge $N$ ($c_1=L$, und $c_i=L$ oder $R$ für $2\le i\le N$).

Das bereitgestellte Bewertungsprogramm gibt den Rückgabewert von polygon aus.

Beschränkungen

• Die Eingabezeichenkette besteht aus $L$ und $R$.

• Es existiert immer mindestens ein Polygon, das durch die Eingabezeichenkette beschrieben wird und die obigen Bedingungen erfüllt.

• $4 \le N \le 800$.

Teilaufgaben

1 (20 Punkte)

• $N \le 10$.

2 (36 Punkte)

• $N \le 40$.

3 (21 Punkte)

• $N \le 100$.

4 (73 Punkte)

• Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

8
LLLRRLLL

Ausgabe 1

6

Eingabe 2

20
LLRLLRRLLRLLRLLRRLLR

Ausgabe 2

15