mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AtCoder これに何時間かけたかと・・・問題:B: 交点 - 東京大学プログラミングコンテスト2014 | AtCoder解法:点(a,b)を通るような直線が,整数座標(p,q),(r,s)を通るとすると,直線の方程式は となる。両辺を1000倍すると, となる。これが点(a,b)を通るので ここで,1000a-1000p,1000b-1000qは整数であり,p,qの値はa,bの値に近づけると,|1000a-1000p| とすれば,上記の等式が成り立ち,かつr-pとs-qの絶対値が10000未満であることが保証される。よって,与えられたx,yに対してx,yに整数値が近いp,qを選んできて,それに対して適切… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2015%2F03%2F29%2F221511" title="東京大学プログラミングコンテスト2014 B:交点 - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%28r-p%29%28y-q%29%20%3D%20%28s-q%29%28x-p%29 Hatena Blog https://hatena.blog 2015-03-29 22:15:11 rich https://mayokoex.hatenablog.com/entry/2015/03/29/221511 1.0 100%