首页 > 代码库 > POJ 3119 Friends or Enemies?
POJ 3119 Friends or Enemies?
先预处理得到各个编号的点的位置再判断 点在二元一次方程的上方还是下方
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include<iostream> #include <algorithm> using namespace std; #define MAXN 11111 #include <queue> #include <vector> struct node { int x, y; }q[66666]; void work(int a,int b) { int ans=0; int x=130,y=130,lon=1; while(ans<=65555) { for(int i=0; i<lon; i++)//zuo { if((x-130)*a+b==y-130) { x--; continue; } q[ans].x=x--; q[ans++].y=y; // printf("%d\n",cost[y][x+1]); } for(int i=0; i<lon; i++)//shang { if((x-130)*a+b==y-130) { y++; continue; } q[ans].x=x; q[ans++].y=y++; // printf("%d\n",cost[y-1][x]); } lon++; for(int i=0; i<lon; i++)//you { if((x-130)*a+b==y-130) { x++; continue; } q[ans].x=x++; q[ans++].y=y; // printf("%d\n",cost[y][x-1]); } for(int i=0; i<lon; i++)//xia { if((x-130)*a+b==y-130) { y--; continue; } q[ans].x=x; q[ans++].y=y--; // printf("%d\n",cost[y+1][x]); } lon++; } } int main() { int a,b,k,t,cas=1; // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); work(a,b); for(int i=0;i<=65555;i++) q[i].x-=130,q[i].y-=130; scanf("%d",&k); printf("Caso %d\n",cas++); for(int i=0; i<k; i++) { int sum1=0,c,d; scanf("%d%d",&c,&d); if(q[c].x*a+b>q[c].y&&q[d].x*a+b>q[d].y) sum1=1; else if(q[c].x*a+b<q[c].y&&q[d].x*a+b<q[d].y) sum1=1; else sum1=0; if(sum1) printf("Mesmo lado da fronteira\n"); else printf("Lados opostos da fronteira\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。