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 中獎了-.-
2011年3月20日星期日
2011年3月3日星期四
[2D Geomtry] 二維線段交點
在本篇 entry 我們談一談二維線段交點求解方法
本人認為，最後討論的 "三角形面積方法" 的解相當優美
中學時期，我們都學過用聯立方程組求 線 / 線交點：
可這個方法缺點是
用代入法 (substitution) 或消元法 (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理
我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內
這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮
將兩條線段表示成：
其中 s, t 分別是 線段AB,CD 的參數
本人認為，最後討論的 "三角形面積方法" 的解相當優美
直線方程組方法
中學時期，我們都學過用聯立方程組求 線 / 線交點：
A x + B y = C
D x + E y = F
可這個方法缺點是
用代入法 (substitution) 或消元法 (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理
我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內
向量方法
這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮
將兩條線段表示成：
P1 = A + s AB -------- (1)
P2 = C + t CD -------- (2)
其中 s, t 分別是 線段AB,CD 的參數
2011年2月27日星期日
SRM 498 - Live
So many familiar handles in my room...
This time 250 and 450 are very easy, but I solved them so slowly... :(
This time 250 and 450 are very easy, but I solved them so slowly... :(
2011年2月17日星期四
隨筆 2011-02-17 - 亂七八糟的寫一篇...
有時候真的發覺「成事在天」
Paper的事... 也由不得我擔心太多
先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...
在我來看，算是好事
Paper的事... 也由不得我擔心太多
先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...
在我來看，算是好事
2011年2月5日星期六
[UVa] Sixth Contest of Newbies
Links：
余以為絕對是值得花時間做的一SET題目...
題目質素高
時限相當緊
Test Data 亦相當狠 (很多 set...)
(題目也相當 "陰"...)
雖然具備基本知識，理論上新手都可以解出起碼三題
不過... 這都包含相當多細節，不是一般的題目呀...
題解概要：
A: Soya Milk - 簡單2D幾何分兩種情況：水平線 touch length/height
B: Closest Fractions - 枚舉
Contest 時 RP較高
預處理GCD後 O(1000^2) 暴試 0.9xx sec 水過了
訂閱：
文章 (Atom)