首页 > 代码库 > SCU 4445 Right turn
SCU 4445 Right turn
模拟。
每次找一下即将要遇到的那个点,这个数据范围可以暴力找,自己的写的时候二分了一下。如果步数大于$4*n$一定是$-1$。
#include<bits/stdc++.h>using namespace std;const int INF = 0x7FFFFFFF;const int mod = 1e9 + 7;const int N = 5e6 + 10;const int M = 1e4 + 1;const double eps = 1e-10;int T,n,m;struct P{ int x,y; P(int X=0,int Y=0) { x=X; y=Y; }}p[2000],q[2000];bool cmp1(P a,P b){ if(a.x!=b.x) return a.x<b.x; return a.y<b.y;}bool cmp2(P a,P b){ if(a.y!=b.y) return a.y<b.y; return a.x<b.x;}int nowx,nowy,nowd;int main(){ while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); q[i].x=p[i].x; q[i].y=p[i].y; } sort(p+1,p+1+n,cmp1); sort(q+1,q+1+n,cmp2); nowx=nowy=0; nowd=0; int ans=0; while(1) { if(nowd==0) { int k = lower_bound(q+1,q+n+1,P(nowx,nowy),cmp2)-q; if(k==n+1||q[k].y!=nowy) { printf("%d\n",ans); break; } else ans++,nowx = q[k].x-1,nowd=(nowd+1)%4; } else if(nowd==2) { int k = lower_bound(q+1,q+n+1,P(nowx,nowy),cmp2)-q-1; if(k==0||q[k].y!=nowy) { printf("%d\n",ans); break; } else ans++,nowx = q[k].x+1,nowd=(nowd+1)%4; } else if(nowd==1) { int k = lower_bound(p+1,p+n+1,P(nowx,nowy),cmp1)-p-1; if(k==0||p[k].x!=nowx) { printf("%d\n",ans); break; } else ans++,nowy = p[k].y+1,nowd=(nowd+1)%4; } else { int k = lower_bound(p+1,p+n+1,P(nowx,nowy),cmp1)-p; if(k==n+1||p[k].x!=nowx) { printf("%d\n",ans); break; } else ans++,nowy = p[k].y-1,nowd=(nowd+1)%4; } if(ans>4*n) { printf("-1\n"); break; } } } return 0;}
SCU 4445 Right turn
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。