線段

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 99(44 users) Total Accepted: 43(39 users) Rating:  Special Judge: No

Description

坐標(biāo)軸上有一些點(diǎn)，依次給出。點(diǎn)與點(diǎn)之間要求用一個(gè)半圓的直徑連接，即把這兩個(gè)點(diǎn)作為連接他們的半圓的直徑的兩個(gè)端點(diǎn)。第一個(gè)點(diǎn)與第二個(gè)點(diǎn)連，第二個(gè)與第三個(gè)連。半圓不能在坐標(biāo)軸下面。問最后連出的圖形，是否存在兩個(gè)半圓他們是交叉的。

Input

多組測試數(shù)據(jù)。 每組測試數(shù)據(jù)的第一行有一個(gè)數(shù)n(1 ≤ n ≤ 1000)，表示有n個(gè)點(diǎn)。 之后一行有n個(gè)數(shù)x1,?x2,?...,?xn (?-?10^6 ≤ xi ≤ 10^6)，每個(gè)數(shù)表示該點(diǎn)在坐標(biāo)軸的位置。

Output

如果最后的圖形有交叉，輸出yes,如果沒有，輸出no。

Sample Input

4 0 10 5 15 4 0 15 5 10

Sample Output

yes no

Source

2014.11.29新生賽-熱身賽

思路：

直接將每個(gè)區(qū)間處理出來，然后O（n^2）暴力判斷兩個(gè)區(qū)間是否相交即可。

Ac代碼：

#include<stdio.h>#include<string.h>#include<iostream>using namespace std;struct node{    int l,r;}b[105000];int a[10500];int main(){    int n;    while(~scanf("%d",&n))    {        int cont=0;        for(int i=0;i<n;i++)        {            scanf("%d",&a[i]);            if(i>0)            {                b[cont].l=min(a[i-1],a[i]);                b[cont].r=max(a[i-1],a[i]);                cont++;            }        }        int flag=0;        for(int i=0;i<cont;i++)        {            for(int j=i+1;j<cont;j++)            {                if(b[j].l>b[i].l&&b[j].l<b[i].r&&b[j].r>b[i].r)                {                    flag=1;                }                if(b[j].r>b[i].l&&b[j].r<b[i].r&&b[j].l<b[i].l)flag=1;            }        }        if(flag==1)PRintf("yes/n");        else printf("no/n");    }}