codeforces 358A Dima and Continuous Line(思想简单，做法暴力)

codeforces 358A Dima and Continuous Line(思维简单，做法暴力)

codeforces 358A  Dima and Continuous Line

题意理解：

给一出个n，然后输入n个数，表示一个一维数组上的坐标点，相邻的两点有连线（首尾两点不相邻）。判断这些连线是否相交，如果相交输出“yes”，否则输出“no”。

思路分析：

首先应该明白什么时候输出“yes”，什么时候输出“no”：

一旦有相交的连线，输出“yes”，后面的一切数据都不必再判断处理，只要输入就好；

如果所有的数据都已经输入并判断处理了，没有发现相交的连线，输出“no”。

然后，怎么判断两条连线是否相交：

若第一条连线的端点是x1,y1(x1<y1),现在给出的连线的端点是x,y(x<y)；

两条连线相交的充分必要条件就是x<x1&&y>x1&&y<y1或x<y1&&x>x1&&y>y1；

两条连线，一旦满足两个条件的其中一个，就说明两条连线相交了。

最后，思路整理，代码编辑。

思路：先输入直到可以比较判断（输入的点大于2），

<1>若n<=2，连线不超过1条，不可能相交，输出“no”

<2>否则，对于现在输入的点和前面一点的连线和前面所有的点的连线进行判断处理，一旦发现有相交现象，输出结果确定为“no”，后面的输入照常，数据部进行比较处理；

      若所有数据输入完成并比较完成，未发现有相交现象，输出结果确定为“yes”。

4926441

Oct 29, 2013 8:47:20 AM

20114045007

358A - Dima and Continuous Line

GNU C++

Accepted

15 ms

0 KB

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int point[1005];
    int n,t;
    int flag;
    int x,y,x1,y1;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        t=0;
        flag=0;  //标记是否相交，相交为1，否则为0
        //先输入2点的坐标，才能判断是否相交；
        //若是点数不超过2，自然不能相交；
        //但是为了后面输入不出错，本组输入必须完成
        scanf("%d",&x);
        point[t++]=x;
        if(n>=2)
            scanf("%d",&x);
        if(n>2)  //弱点数超过2，判断是否相交
        {
            point[t++]=x;
            n-=2;
            while(n--)  //将后面的点输入，同时判断该点和前面已点的连线是否有相交情况
            {
                scanf("%d",&y);
                if(flag)continue;  //前面判断已经证明有相交情况，不必再判断
                point[t++]=y;
                if(x>y)swap(x,y);  //将当前要判断的两点先小后大
                for(i=0;i<t-1;i++)  //将该连线和前面所有连线比较处理，看是否相交
                {
                    x1=point[i];
                    y1=point[i+1];  //取前面某条连线与该连线比较处理，看是否相交
                    if(x1>y1)swap(x1,y1);
                    if(x<x1&&y>x1&&y<y1||x<y1&&x>x1&&y>y1)  //判断是否相交
                    {
                        flag=1;
                        break;
                    }
                }
                x=point[t-1];
            }
        }
        printf(flag?"yes":"no");
        printf("\n");
    }
    return 0;
}