首页 > 代码库 > SCU Right turn

SCU Right turn

2024-09-18 14:41:41   222人阅读

Right turn

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.

Input

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)

Output

For each test, write 1

integer which denotes the number of turns, or ``-1‘‘ if she makes infinite turns.

Sample Input

    2    1 0    0 -1    1    0 1    4    1 0    0 1    0 -1    -1 0

Sample Output

    2    0    -1
分析：用STL模拟比较好写，另外注意判断-1的转向次数；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=1e5+10;const int N=1e3+10;using namespace std;inline int id(int l,int r){return l+r|l!=r;}ll gcd(ll p,ll q){return q==0?p: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;void turn_r(int x,int y);void turn_d(int x,int y);void turn_l(int x,int y);void turn_u(int x,int y);void turn_r(int x,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;}void turn_d(int x,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;}void turn_l(int x,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;}void turn_u(int x,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");        else printf("%d\n",cnt);    }    return 0;}

SCU Right turn


联系
我们