题目链接:http://codeforces.com/problemset/problem/358/A
题目意思:在横坐标上给出n个不同的点,需要把前一个点跟后一个点(这两个点的顺序是紧挨着的)用一个半圆弧来连接。现在要判断的是这些符合条件的点连接以后,圆弧之间是否相交了。是则输出yes,否则输出no。
假设序列是x1,x2,x3,x4.....xn。相交其实只有两种情况,第一种就是样例已经给出了的:即 x1 < x3 < x2 且 x2 < x4。另外一种情况就是第一种情况的对称位置x3 < x1 且 x1 < x4 < x2。
要特别注意的是,由于序列中前后两个数不是按从小到大的顺序排好的,因此要先确保前一个数要大于后一个数。另外,当n <= 3时,是绝对不会发生交叉的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 const int maxn = 1000 + 10; 7 int a[maxn], tmp1[5], tmp2[5]; 8 9 int main() 10 { 11 int i, j, n, flag; 12 while (scanf("%d", &n) != EOF) 13 { 14 // freopen("in.txt", "r", stdin); 15 for (i = 0; i < n; i++) 16 { 17 scanf("%d", &a[i]); 18 } 19 if (n <= 3) 20 { 21 printf("no "); 22 } 23 else 24 { 25 flag = 0; 26 for (i = 2; i < n-1; i++) 27 { 28 if (a[i] > a[i+1]) 29 { 30 tmp1[0] = a[i+1]; 31 tmp1[1] = a[i]; 32 } 33 else 34 { 35 tmp1[0] = a[i]; 36 tmp1[1] = a[i+1]; 37 } 38 // printf("tmp1[0] = %d, tmp1[1] = %d ", tmp1[0], tmp1[1]); 39 for (j = 0; j < n-1; j++) 40 { 41 if (a[j] > a[j+1]) 42 { 43 tmp2[0] = a[j+1]; 44 tmp2[1] = a[j]; 45 } 46 else 47 { 48 tmp2[0] = a[j]; 49 tmp2[1] = a[j+1]; 50 } 51 if ((tmp1[0] > tmp2[0] && tmp1[0] < tmp2[1] && tmp1[1] > tmp2[1]) || (tmp1[0] < tmp2[0] && tmp1[1] > tmp2[0] && tmp1[1] < tmp2[1])) 52 { 53 flag = 1; 54 // printf("tmp1[0] = %d, tmp1[1] = %d ", tmp1[0], tmp1[1]); 55 // printf("tmp2[0] = %d, tmp2[1] = %d ", tmp2[0], tmp2[1]); 56 goto h; 57 } 58 } 59 } 60 h: if (!flag) 61 printf("no "); 62 else 63 printf("yes "); 64 } 65 } 66 return 0; 67 }