PKU 3119 Friends or Enemies?
http://poj.org/problem?id=3119
原点を中心にある直線の上にない座標に番号をつけていく。
このとき、ある2つの番号が直線に対して同じ側にあるかを判定しろというような問題。
座標に番号付けしてどちらにあるかを判定すればいい。
int a,b; string out[]={ "Lados opostos da fronteira", "Mesmo lado da fronteira", }; PI co[100000]; bool lower(int n){ return a*co[n].F+b<co[n].S; } void solve(){ cin>>a>>b; int sz=0; int cx=0,cy=0; int di=2; while(sz<100000){ if(cx*a+b!=cy) co[sz++]=mp(cx,cy); if(abs(cx)==abs(cy))++di; if(cx==cy && cx<=0)--cx,--cy,di=0; cx+=dx[di]; cy+=dy[di]; di&=3; } int N; cin>>N; rep(i,N){ int m,n; cin>>m>>n; cout<<out[lower(m)==lower(n)]<<endl; } } main(){ int t; cin>>t; rep(ca,t){ printf("Caso %d\n",ca+1); solve(); } }