#include<stdio.h>

#include<iostream>

#include<math.h>

using namespace std;

const double EPS = 1e-6;

int sign(double d)

{

return d < -EPS? -1 :(d > EPS? 1 : 0);

}

bool equ(double a,double b)

{

return sign(a-b) == 0;

}

class XPoint

{

public:

int x,y;

XPoint* next;

XPoint(int _x,int _y) :x(_x),y(_y),next(NULL)

{

}

};

class XLine

{

public:

float a,b,c;

float len;//st,ed 的 向量长度

XLine(XPoint* st, XPoint* ed)

{

a = ed->y - st->y;

b = st->x - ed->x;

c = st->y * ed->x - st->x * ed->y;

len = sqrt(a*a + b*b);

}

};

float dis_p2_line(XPoint* p, XLine* l)

{

return fabs(l->a * p->x + l->b * p->y + l->c) / l->len;

}

bool line_cross_grid(XLine* l, XPoint* p)

{

float dis = dis_p2_line(p,l);

return dis < 0.71;

}

bool equ(XPoint* a,XPoint* b)

{

return (a->x == b->x && a->y == b->y);

}

XPoint* GetKey(XPoint* st, XPoint* ed)

{

XPoint* p = st;

XLine* line = new XLine(st,ed);

int Asign = sign(line->a);

int Bsign = -sign(line->b);

while(true)

{

int x = p->x;

int y = p->y;

XPoint* p1 = new XPoint(x ,y + Asign);

XPoint* p2 = new XPoint(x + Bsign , y);

if(Asign)

{

if( line_cross_grid( line, p1 ))

{

p->next = p1;

p = p->next;

}

if( equ(p1, ed) )break;

}

if(Bsign)

{

if( line_cross_grid( line, p2 ))

{

p->next = p2;

p = p->next;

}

if( equ(p2, ed) )break;

}

}

p = st;

while(p)

{

cout<<p->x <<" " << p->y<<endl;

p = p->next;

}

return st;

}

int main()

{

XPoint* st = new XPoint(2,4);

XPoint* ed = new XPoint(2,10);

GetKey(st, ed);

return 0;

}