UVa 11164 -- Kingdom Division

簡單題，不過很少人 submit。

要衝高名次，除了讓演算法比別人快，最好還是 submit 很少人寫的題目。

如果某題沒有人 AC，你 AC 了，肯定是第一名無誤。



http://uva.onlinejudge.org/external/111/11164.html

這題是數學題，拉出輔助線 AX 利用面積比例關係，國中水準數學就能解題。

底下把註解貼上來，

https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_11164.cc 也有放一份。

// Connect the line segment AX and quadrilateral AEXF is divided into
// two pieces: triangle AEX and triangle AFX.
//
// Let x = [AEX], area of triangle AEX; y = [AFX], area of triangle AFX.
//
// (1) On the line segment BE:
// [ABX] : [AEX] = BX : EX = [CBX] : [CEX]
// <=> (a+y) : x = b : c <=> bx = c(a+y).
//
// (2) On the line segment CF:
// [AFX] : [ACX] = FX : CX = [BFX] : [BCX]
// <=> y : (c+x) = a : b <=> by = a(c+x).
//
// By (1)(2), solve x and y in terms of a, b, c.
// The result will be x+y = ac(a+2b+c)/(b^2 - ac) if b^2 - ac > 0.
//
// Note that a and c are symmetric. So if we exchange a and c,
// the result will not be changed (sanity check).

某方面來說，程式的可讀性要自己來做，不能光抱怨別人。

a*c*(a + 2*b + c)/(b*b - a*c) 算是蠻不能解釋的運算。