num esc pause sample hat integer sta each
frog is trapped in a maze. The maze is infinitely large and divided into grids. It also consists of n
obstacles, where the i-th obstacle lies in grid (xi,yi)
.
frog is initially in grid (0,0)
, heading grid (1,0)
. She moves according to The Law of Right Turn: she keeps moving forward, and turns right encountering a obstacle.
The maze is so large that frog has no chance to escape. Help her find out the number of turns she will make.
The input consists of multiple tests. For each test:
The first line contains 1
integer n (0≤n≤103). Each of the following n lines contains 2 integers xi,yi. (|xi|,|yi|≤109,(xi,yi)≠(0,0), all (xi,yi)
are distinct)
For each test, write 1
integer which denotes the number of turns, or ``
'' if she makes infinite turns.
- -1
- 2
- 1 0
- 0 -1
- 1
- 0 1
- 4
- 1 0
- 0 1
- 0 -1
- -1 0
- 2
- 0
- -1分析:用STL模拟比较好写,另外注意判断-1的转向次数;代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include <string>
- #include <set>
- #include
- #include
- #include
- #include
- #include
- #definerep(i,m,n) for(i=m;i<=n;i++)#definemod 1000000007#defineinf 0x3f3f3f3f#definevi vector
- #definepb push_back#definemp make_pair#definefi first#definese second#definell long long#definepi acos(-1.0)#definepii pair
- #definesys system("pause")const intmaxn=1e5+10;
- const intN=1e3+10;
- using namespace std;
- inline intid(intl,intr){returnl+r|l!=r;}
- ll gcd(ll p,ll q){returnq==0p:gcd(q,p%q);}
- ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
- int n,m,k,t,cnt;
- map<int,set<int> >pq1,pq2;
- set<int>::iterator it;
- bool flag;
- voidturn_r(intx,int y);
- voidturn_d(intx,int y);
- voidturn_l(intx,int y);
- voidturn_u(intx,int y);
- voidturn_r(intx,int y)
- {
- it=pq2[y].lower_bound(x);
- if(it!=pq2[y].end())
- {
- if(++cnt>2*n)
- {
- flag=false;
- return;
- }
- x=*it-1;
- turn_d(x,y);
- }
- else return;
- }
- voidturn_d(intx,int y)
- {
- it=pq1[x].lower_bound(y);
- if(it!=pq1[x].begin())
- {
- --it;
- if(++cnt>2*n)
- {
- flag=false;
- return;
- }
- y=*it+1;
- turn_l(x,y);
- }
- else return;
- }
- voidturn_l(intx,int y)
- {
- it=pq2[y].lower_bound(x);
- if(it!=pq2[y].begin())
- {
- --it;
- if(++cnt>2*n)
- {
- flag=false;
- return;
- }
- x=*it+1;
- turn_u(x,y);
- }
- else return;
- }
- voidturn_u(intx,int y)
- {
- it=pq1[x].lower_bound(y);
- if(it!=pq1[x].end())
- {
- if(++cnt>2*n)
- {
- flag=false;
- return;
- }
- y=*it-1;
- turn_r(x,y);
- }
- else return;
- }
- int main()
- {
- int i,j;
- while(~scanf("%d",&n))
- {
- pq1.clear();
- pq2.clear();
- flag=true;
- cnt=0;
- rep(i,1,n)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- pq1[x].insert(y);
- pq2[y].insert(x);
- }
- turn_r(0,0);
- if(!flag)puts("-1");
- elseprintf("%d\n",cnt);
- }
- return 0;
- }
SCU Right turn
来源: http://www.bubuko.com/infodetail-2048298.html