東京大学プログラミングコンテスト2014 B:交点
これに何時間かけたかと・・・
問題:B: 交点 - 東京大学プログラミングコンテスト2014 | AtCoder
解法:点(a,b)を通るような直線が,整数座標(p,q),(r,s)を通るとすると,直線の方程式は
となる。両辺を1000倍すると,
となる。これが点(a,b)を通るので
ここで,1000a-1000p,1000b-1000qは整数であり,p,qの値はa,bの値に近づけると,|1000a-1000p| < 1000などと抑えることができる。また,
とすれば,上記の等式が成り立ち,かつr-pとs-qの絶対値が10000未満であることが保証される。よって,与えられたx,yに対してx,yに整数値が近いp,qを選んできて,それに対して適切にs,rを選べば良い。
本番はここまでの解法は思いついたが,x,yから1000倍して整数値に戻すところで間違えていた。辛い。
以下ソースコード
int X, Y; int solve(int p, int q) { if (1000*p == X && 1000*q == Y) { printf("%d %d %d %d\n", p, q, p+1, q+1); return 0; } else if (1000*p == X) { int r = p; printf("%d %d %d %d\n", p, q, r, q+1); return 1; } else if (1000*q == Y) { int s = q; printf("%d %d %d %d\n", p, q, p+1, s); return 0; } else { int s = Y-999*q; int r = X-999*p; printf("%d %d %d %d\n", p, q, r, s); return 0; } } int main() { double x, y; cin >> x >> y; int signx = 1, signy = 1; if (x*1000 < 0) signx = -1; if (y*1000 < 0) signy = -1; X = signx*(int)(1000*signx*x+0.5), Y = signy*(int)(1000*signy*y+0.5); int p = X / 1000; int q = Y / 1000; int tmp = solve(p, q); p += 5; q += 3; solve(p, q); return 0; }