UTPC 2014 : B - 交点

結構迷った。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_b

問題

2次元座標上の点(x,y)が与えられる。
x,yは小数点以下第3位まである可能性がある。
格子点2点を通る2本の直線対であり、(x,y)で交わるようなものを求め、格子点を求めよ。

解法

(x,y)を通る直線を2つ求めればよい。
Editorialによると、(x,y)周辺の適当な格子点(a,b)があったとき、(a,b)→(x,y)を1000倍伸ばした点(a',b')を求めれば、そこは格子点となるので(a,b)-(a',b')は解となる。

自分は(x,y)が整数のときだけはそれぞれ直線を求めてしまった。

double X,Y;
int XX,YY;
bool DX,DY;

void output(int x1,int y1,int x2,int y2) {
	x1/=1000;
	x2/=1000;
	y1/=1000;
	y2/=1000;
	if(DX) x1=-x1, x2=-x2;
	if(DY) y1=-y1, y2=-y2;
	_P("%d %d %d %d\n",x1,y1,x2,y2);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	XX=X*1000+(X>0?0.5:-0.5);
	YY=Y*1000+(Y>0?0.5:-0.5);
	if(XX<0) DX=true, XX=-XX;
	if(YY<0) DY=true, YY=-YY;
	
	if(XX%1000==0 && YY%1000==0) {
		output(XX,-1000,XX,1000);
		output(-1000,YY,1000,YY);
		return;
	}
	int ty=YY/1000*1000, ry=YY-ty;
	int tx=XX/1000*1000, rx=XX-tx;
	
	if(XX%1000==0) {
		output(XX,-1000,XX,1000);
		output(XX-1000*ry,ty,XX+1000*(1000-ry),ty+1000);
		return;
	}
	if(YY%1000==0) {
		output(-1000,YY,1000,YY);
		output(tx,YY-1000*rx,tx+1000,YY+1000*(1000-rx));
		return;
	}
	output(tx,ty,tx+1000*rx,ty+1000*ry);
	output(tx,ty+1000,tx+1000*rx,ty+1000-1000*(1000-ry));
}

まとめ

結構迷ったけどわかってしまうとあっさり。