[東方] 我沒辦法幫琪露諾找到寶藏了

[gggiantguy (莫笑)]

http://i.imgur.com/lpY0c1t.jpg
http://i.imgur.com/YZZTKem.jpg
我就是那個笨蛋
我知道把A、B當成圓的直徑
圓周上每一點都可以變直角三角形
但是再然後怎麼求點座標……

--
https://imgur.com/bjxF4BZ
From #01 Undertaker, to #23 Handler One.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.253.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1762607367.A.0CE.html
推 chinnez: https://i.imgur.com/XgsapNC.jpeg
推 zxcv7892341: 八嘎八嘎
推 hary5155: 我對天文密葬法稍微比較有興趣w
推 kirimaru73: 這是要你寫程式 所以還有幻想鄉沒有編譯器的問題
推 ainamk: 編譯器就是那個八雲藍 不用太擔心
推 e5a1t20: a^2+b^2=c^2 驗證簡單，但要怎麼找比較快我就不知道了
推 kirimaru73: 仔細看了題意 他只是要你找一個座標給笨蛋探險而已
→ kirimaru73: 那裡到底有沒有寶藏不在你的責任範圍內
推 GY426: 直接窮舉 計算有沒有符合畢氏定理吧 再快就是圓跟兩條切線
推 kirimaru73: 真正麻煩的應該是輸入兩點在同一行或同一列上
→ kirimaru73: 然後彼此距離是奇數 這樣可能會真的要窮舉搜尋
→ kirimaru73: 不同行列 或 同一行列但距離偶數 直接傳簡單解就好了
→ ainamk: 不在同一行或同一列的話就A點的x座標+B點的y座標
→ kirimaru73: 題意有寫你不用對寶藏負責 你只要吐出座標就好
推 emptie: AB都是格子點，所以(x,y) (z,w) 作為斜邊的話， (x,w) 與
→ kaomark: 若x1!=x2且y1!=y2那x1,y2或者x2,y1就是解了
→ emptie: (z,y) 都是符合條件的點
→ kaomark: 如果有相等的再看x還y哪個數字加減1就也能當解啊
→ kirimaru73: 同一行列距離偶數：直接頂一個範圍內的45度給他
→ emptie: 再處理在座標一樣的情況
→ kirimaru73: 啊對 幹 我是笨蛋 我被直角的位置所束縛了
→ kirimaru73: 所以這題實際上不用搜尋
推 iampig951753: 跟老高同一間
→ ainamk: 座標完全一樣要在輸入那邊就排除 這個倒是簡單
→ kirimaru73: 寫搜尋的會大中計 因為可能會搜不到解
→ kirimaru73: 但實際上只要輸入合法就一定有解
→ kirimaru73: 測試資料一定會準備這種橫向搜尋會爆的內容來堵人
→ ainamk: 其實這出題也有點微妙 東方+程設應該要算三途川的寬度才對
推 kirimaru73: 這範圍意思是保你int32夠用
→ kirimaru73: 然後如果你中計了想用暴力搜尋 你會覺得要用int64
→ kirimaru73: (用浮點數的話大數字平方精確度會報掉)
→ kirimaru73: 結果第一筆測試資料是0 0 0 1 你搜尋不出來 整題零分
→ ainamk: 我程設只有皮毛 int64會出什麼問題?
推 kirimaru73: 不是int64的問題 是你以為輸入兩點必是斜邊的問題
→ kirimaru73: 題目實際上沒這個條件 所以他敢保證一定有解
→ kirimaru73: 但你一定是誤以為有這個條件才會走到畢氏定理搜尋
推 e5a1t20: 我剛剛想到只要一組解，最快就是找等腰直角三角形
→ e5a1t20: 像0 0 4 2，就直接給2 -4，出界還有三組解可以試
→ ainamk: 他給你的點AB未必會有等腰直角三角形的格子點解
→ e5a1t20: 對，的確不能保證有解
→ ainamk: 轉90度雖然是很簡單暴力的作法但很容易超出範圍
→ e5a1t20: 實際解應該是兩條垂直線，還有以兩點為直徑的圓
→ ainamk: 他給你的是兩個格子點所以兩條垂直線你已經有了 不需要圓
→ e5a1t20: 可是剛剛才說格子點不一樣有解，有可能出界，然後給你狠
→ e5a1t20: 一點來個xy互質的座標，保證中間找不到整數點
→ e5a1t20: *不一定有解
推 kirimaru73: 一定有解 題目的保證有解的意思其實是這樣：
→ kirimaru73: 「如果你能想到其實這麼簡單，那當然一定有解」
→ kirimaru73: 範圍是正方形不是圓形 不同行列輸入你就吐一個直角點
→ kirimaru73: 同行列輸入你就轉90度加一或減一(確認邊界方向)
→ ainamk: 不只保證有解而且保證兩個   但講出有兩個等於破梗XD
→ kirimaru73: 如果是其它製造直角三角形的方式 出題者的測試資料一
→ kirimaru73: 定會準備那種方式會爆掉的輸入
→ kirimaru73: 只要你任何一筆資料答不出來 他甚至有理由給整題零分
推 jpadesky: 他的問題對人很好耶，在實數上求點
→ ainamk: xy座標軸上不會出現實數以外的東西吧…
推 kirimaru73: 這題比較微妙的是 他是程式題 程式沿著一個方向搜尋
→ kirimaru73: 是很合理的想像 但這題只要一想到搜尋就是死
→ ainamk: 比較大的問題是原po給了一個很大的雜音讓人會想要搜尋XD
→ ainamk: 不然你看例題裡的輸入輸出應該很直覺會想到拉長方形
推 kirimaru73: 我看到例題有想到當斜邊就很簡單 然後「如果同行列的
→ kirimaru73: 話就沒這麼簡單了」 然後就爆了
→ logstar11: 先平移讓任一點為原點 在取剩下那個點的隨便軸投影
→ ainamk: 平移到原點可能會讓另一點跑出定義範圍 直接取(x1,y2)就好
推 usoko: 「有多解輸出任意一組即可」 那就超簡單了 又不是要你算有
→ usoko: 幾種解....
推 civic0960: 這算基礎題吧 感覺大學程設寫過類似的
推 neetarashi: 斜邊的情況x1!=x2 y1!=y2輸出x1 y2就好
→ neetarashi: 反過來說ifx1==x2 的情況就是輸出x1+1 y1
→ neetarashi: 同理處理y1==y2 暴力破解法
→ neetarashi: 但這種題目很可能會有10^9做邊的情況去gank +1
→ neetarashi: 所以要選座標小的那邊去加 應該就能符合條件了
→ soem: 加個判斷，盡量往原點歪過去就好了；阿但是2^32不會爆啦
→ soem: 喔對喔，超出定義域了，還是要避開