円周上のCrossing 〜 横へな 2013.9.28 参考問題

問題

円周上に名前のついた点がある。同じ名前の点を直線で結ぶ。直線と直線の交点のうち、円の内部にあるものの数を数えよ。

ただし、3本以上の直線が1点で交わっているような気がする場合には交点がほんのちょっとずれているものとして数えること。(つまり、3本が1点で交わっていたら交点は3個。4本なら6個と数える。)

点の数は、高々100個程度と思ってよい。

入力と出力

点の名前は英数字1文字。大文字と小文字を区別する。

入力は、点の名前を区切り文字なしで aabbca1bcb のように並べたものである。

出力は、交点の数を10進数で表現した 14 のような文字列とする。

補足

サンプルデータ

# 入力 期待
0 aabbca1bcb 14
1 111ZZZ 0
2 v 0
3 ww 0
4 xxx 0
5 yyyy 1
6 zzzzz 5
7 abcdef 0
8 abcaef 0
9 abbaee 0
10 abcacb 2
11 abcabc 3
12 abcdabcd 6
13 abcadeabcade 23
14 abcdeedcba 0
15 abcdeaedcba 8
16 abcdeaedcbad 16
17 QQQQXXXX 2
18 QwQQmQXmXXwX 14
19 111222333 0
20 aaAAaA 4
21 121232313 12
22 1ab1b 1
23 abcdefbadcfe 12
24 abxcdefbadcfex 14
25 dtnwtkt 0
26 mvubvpp 0
27 moggscd 0
28 kzkjzpkw 2
29 fbifybre 1
30 rrrfjryki 1
31 wrbbdwsdwtx 2
32 vvucugvxbvgx 9
33 ojkjzyasjwbfjj 5
34 ggffyuxnkyypifff 5
35 vcgtcqlwrepwvkkogl 4
36 xeqtmmgppwcjpcisogxbs 4
37 lukltpeucrqfvcupnpxwmoj 6
38 zpzswlkkoqwwndwpfdpkhtzgtn 31
39 bkfeflagfvluelududqjcvfyvytfw 45
40 rvqbhfmcjjqlpqzulzerxgyowiwrfkmhw 26
41 qyxvpdtoeexbqsethwjwmqszcxxjnsdoeaet 144
42 rjmsgmswhcolmpbhmpncziymydyalrcnevsrespj 133
43 oxetnyjzjbysnwktfwzndlejfndsqeetsnjvsicyjehd 395
44 wzvddnddzogywcqxbyvagbzmsmtcmrrlbnebmvhaemjouaqim 219
45 karhphxcxqgsyorhusbumbqzocuzvnwzwcpxgsksrviihxrgsrhji 461
46 oxgbononhqdxzmkysgijwvxljpaazmgkurkpffeuwywwuyxhyfkicgyzyc 441
47 sdgsrddwsrwqthhdvhrjhgtxwgurgyiygtktgtughtogzaqmcafkljgpniddsvb 1077
48 qemhecchkgzhxmdcsltwhpoyhkapckkkzosmklcvzkiiucrvzzznmhjfcdumuflavxik 1711
49 ffqmsirwpxrzfkbvmmfeptkbhnrvfcywthkwkbycmayhhkgvuyecbwwofwthlmzruphrcujwhr 2440

C/C++/Java 用のテストデータ