2656 - 吴壕画圆

吴壕最近喜欢上了在一个一维坐标轴上画圆，并且由这个画圆引起了一个深思，给你一个数字的序列，然后以每相邻的两个点的连线为直径画圆，问是否有交叉，但是呢，吴壕对自己出的问题表示束手无策，于是去问学霸，学霸扫了一眼说：这种弱智的问题不要问我。于是吴壕来问你们这个问题了。

Ps:点“提示”可看图

Input

多组输入，每组数据先输入一个n(n<=100)表示n个数，然后输入n个数，表示这个数字序列(每个数在-10^6--10^6之间)。

Output

如果有交叉输出yes 否则输出no

Examples

Input

Output

yes
no

Solution C

#include<stdio.h>

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int a[100];
		int i,j,flog=0,t,t1;
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n-1;i++)
		{
			if(a[i]>a[i+1])
			{
				t=a[i];
				a[i]=a[i+1];
				a[i+1]=t;
			}
			
			for(j=i+1;j<n-1;j++)
			{
				
				if( (a[j]>a[i]&&a[j]<a[i+1]&& (a[j+1]>a[i+1]||a[j+1]<a[i]) )||(a[j+1]>a[i]&&a[j+1]<a[i+1]&& (a[j]>a[i+1]||a[j]<a[i])) )
				{
					printf("yes\n");
					flog=1;
					break;
				}
			}
			if(flog==1)
				break;

		}
		if(flog==0)
			printf("no\n");
	}
	return 0;
}

Solution C++

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1005];
struct kk{
  int zhi;
  int xuhao;
}b[1005];
bool cmp(kk a,kk b)
{
    return a.zhi<b.zhi;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i].zhi=a[i];
        b[i].xuhao=i;
    }
    sort(b,b+n,cmp);
    for(int i=0;i<n;i++)
    a[b[i].xuhao]=i+1;
    //for(int i=0;i<n;i++)
       // printf("%d ",a[i]);
    int k=a[0];
    int max=n,min=1;
    int flag=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]-k==1||k-a[i]==1)
        {  //cout<<1<<endl;
            max--;
            for(int j=i;j<n;j++)
             {
                 if(a[j]>k)
                   a[j]--;
             }

            k=a[i];
        }
        else if(k==max||k==min)
        {  //cout<<2<<endl;
            if(k==max&&a[i]==min)
            {
                max--;
            }
            else if(k==min&&a[i]==max)
                min++;
            else flag=1;
            k=a[i];
        }
        else flag=1;
        if(flag==1) break;
    }
   // cout<<max<<" "<<min<<endl;
    if(flag==1) printf("yes\n");
    else printf("no\n");
    }
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题