2011-03-23 Team Training - World Finals 2004

2011-03-23 Wed
HKG Time - 1900 to 2400

啱啱尋晚係 research deadline 後
第二次正式齊腳 training

今次做 World Finals 2004
悲劇呀！

• 題目 (Live Archive)
• Scoreboard

SRM 500 - Live

500大賽...
很難的一SET題目

250 我花了 45+ 分鐘才通過 sample...
不過縱使通過 sample 也不代表甚麼...
預期會有大量 fail system test 出現...
對自己的 submission 也沒有大期望...........

其後我看了 500
長方形的四個角落是整數座標
所以，我想大概算法是先預處理每一個格子
[x, x+1) × [y, y+1)
所包括的線段總長度吧
DFS 就好了，深度大約去到第六層
有想法，式子也準備好
但沒有足夠時間實現，更別說測試了...

但感覺 500 若能通過 sample
比起 250，應該有更大機會通過 system test

Petr 等一眾高手完成了全部 3 題...

---

rng_58 單做 1000 Rank 6th

Judge 完了
250 通過了
Rank 4th in room → 沒錢分 sosad

---

甚麼?!
lucky draw 中獎了-.-

[2D Geomtry] 二維線段交點

在本篇 entry 我們談一談二維線段交點求解方法
本人認為，最後討論的 "三角形面積方法" 的解相當優美

---

直線方程組方法

中學時期，我們都學過用聯立方程組求 線 / 線交點：

A x + B y = C
D x + E y = F

可這個方法缺點是
用代入法 (substitution) 或消元法  (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理

我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內

---

向量方法

這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮

將兩條線段表示成：

P₁ = A + s AB -------- (1)
P₂ = C + t CD -------- (2)

其中 s, t 分別是 線段AB,CD 的參數