列表

详情

MMT1. 交叉线

描述

大M布置给小M一个题目：首先给出n个在横坐标上的点，然后连续的用半圆连接他们：首先连接第一个点与第二点(以第一个点和第二点作为半圆的直径)。然后连接第二个第三个点，直到第n个点。现在需要判定这些半圆是否相交了，在端点处相交不算半圆相交。如下图所示。

输入描述

输入的第一行包含一个整数T (1 ≤ T ≤ 10)表示有T组样例。

每组样例的第一行是一个整数n (1≤n≤1000)。

接下来的一行输入有n个用空格隔开的不同的整数a1,a2,...,an (-1000000 ≤ ai ≤ 1000000)，(ai,0)表示第i个点在横坐标的位置。

输出描述

对于每个输入文件，输出T行。

每行输出"y"表示这些半圆有相交或者"n"。

示例1

输入: 

2
4
0 10 5 15
4
0 15 5 10

输出: 

y
n

原站题解

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2020-10-31 

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
   
using namespace std;
   
bool func(int n, int* nums)
{
    int i, j;
    int out_b[2] = { -2000000, 2000000 };
    int in_b[2] = { 0 };
    int flag, flag_before;
    for (i = 1; i < n; i++) {
        flag = nums[i] < nums[i - 1];
        if (i == 1) {
            flag_before = flag;
            continue;
        }
   
        if (flag == flag_before) {
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            if (in_b[0] == 0 && in_b[1] == 0) {
                in_b[0] = min(nums[i-2], nums[i - 1]);
                in_b[1] = max(nums[i-2], nums[i - 1]);
            }
            else {
                in_b[0] = min(nums[i - 1], in_b[0]);
                in_b[1] = max(nums[i - 1], in_b[1]);
            }
        }
        else if (flag != flag_before) {
            if (nums[i] > in_b[0] && nums[i] < in_b[1])
                return true;
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            int left = min(nums[i - 1], nums[i - 2]);
            int right = max(nums[i - 1], nums[i - 2]);
            if (nums[i] > left && nums[i] < right) {
                out_b[0] = left; out_b[1] = right;
                in_b[0] = 0; in_b[1] = 0;
            }
            else {
                if (in_b[0] == 0 && in_b[1] == 0) {
                    in_b[0] = left; in_b[1] = right;
                }
                else {
                    in_b[0] = min(nums[i - 1], in_b[0]);
                    in_b[1] = max(nums[i - 1], in_b[1]);
                }
            }
        }
        flag_before = flag;
    }
    return false;
}
   
int main()
{
    int T, n;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        int* nums = new int[n];
        for (int j = 0; j < n; j++)
            scanf("%d", &nums[j]);
        if (func(n, nums))
            printf("y\n");
        else
            printf("n\n");
        delete[] nums;
    }
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 380KB, 提交时间: 2020-10-31 

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
   
using namespace std;
   
bool func(int n, int* nums)
{
    int i, j;
    int out_b[2] = { -2000000, 2000000 };
    int in_b[2] = { 0 };
    int flag, flag_before;
    for (i = 1; i < n; i++) {
        flag = nums[i] < nums[i - 1];
        if (i == 1) {
            flag_before = flag;
            continue;
        }
   
        if (flag == flag_before) {
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            if (in_b[0] == 0 && in_b[1] == 0) {
                in_b[0] = min(nums[i-2], nums[i - 1]);
                in_b[1] = max(nums[i-2], nums[i - 1]);
            }
            else {
                in_b[0] = min(nums[i - 1], in_b[0]);
                in_b[1] = max(nums[i - 1], in_b[1]);
            }
        }
        else if (flag != flag_before) {
            if (nums[i] > in_b[0] && nums[i] < in_b[1])
                return true;
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            int left = min(nums[i - 1], nums[i - 2]);
            int right = max(nums[i - 1], nums[i - 2]);
            if (nums[i] > left && nums[i] < right) {
                out_b[0] = left; out_b[1] = right;
                in_b[0] = 0; in_b[1] = 0;
            }
            else {
                if (in_b[0] == 0 && in_b[1] == 0) {
                    in_b[0] = left; in_b[1] = right;
                }
                else {
                    in_b[0] = min(nums[i - 1], in_b[0]);
                    in_b[1] = max(nums[i - 1], in_b[1]);
                }
            }
        }
        flag_before = flag;
    }
    return false;
}
   
int main()
{
    int T, n;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        int* nums = new int[n];
        for (int j = 0; j < n; j++)
            scanf("%d", &nums[j]);
        if (func(n, nums))
            printf("y\n");
        else
            printf("n\n");
        delete[] nums;
    }
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 400KB, 提交时间: 2020-11-01 

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
   
using namespace std;
   
bool func(int n, int* nums)
{
    int i, j;
    int out_b[2] = { -2000000, 2000000 };
    int in_b[2] = { 0 };
    int flag, flag_before;
    for (i = 1; i < n; i++) {
        flag = nums[i] < nums[i - 1];
        if (i == 1) {
            flag_before = flag;
            continue;
        }
   
        if (flag == flag_before) {
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            if (in_b[0] == 0 && in_b[1] == 0) {
                in_b[0] = min(nums[i-2], nums[i - 1]);
                in_b[1] = max(nums[i-2], nums[i - 1]);
            }
            else {
                in_b[0] = min(nums[i - 1], in_b[0]);
                in_b[1] = max(nums[i - 1], in_b[1]);
            }
        }
        else if (flag != flag_before) {
            if (nums[i] > in_b[0] && nums[i] < in_b[1])
                return true;
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            int left = min(nums[i - 1], nums[i - 2]);
            int right = max(nums[i - 1], nums[i - 2]);
            if (nums[i] > left && nums[i] < right) {
                out_b[0] = left; out_b[1] = right;
                in_b[0] = 0; in_b[1] = 0;
            }
            else {
                if (in_b[0] == 0 && in_b[1] == 0) {
                    in_b[0] = left; in_b[1] = right;
                }
                else {
                    in_b[0] = min(nums[i - 1], in_b[0]);
                    in_b[1] = max(nums[i - 1], in_b[1]);
                }
            }
        }
        flag_before = flag;
    }
    return false;
}
   
int main()
{
    int T, n;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        int* nums = new int[n];
        for (int j = 0; j < n; j++)
            scanf("%d", &nums[j]);
        if (func(n, nums))
            printf("y\n");
        else
            printf("n\n");
        delete[] nums;
    }
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 504KB, 提交时间: 2020-07-28 

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
    
using namespace std;
    
bool func(int n, int* nums)
{
    int i, j;
    int out_b[2] = { -2000000, 2000000 };
    int in_b[2] = { 0 };
    int flag, flag_before;
    for (i = 1; i < n; i++) {
        flag = nums[i] < nums[i - 1];
        if (i == 1) {
            flag_before = flag;
            continue;
        }
    
        if (flag == flag_before) {
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            if (in_b[0] == 0 && in_b[1] == 0) {
                in_b[0] = min(nums[i-2], nums[i - 1]);
                in_b[1] = max(nums[i-2], nums[i - 1]);
            }
            else {
                in_b[0] = min(nums[i - 1], in_b[0]);
                in_b[1] = max(nums[i - 1], in_b[1]);
            }
        }
        else if (flag != flag_before) {
            if (nums[i] > in_b[0] && nums[i] < in_b[1])
                return true;
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            int left = min(nums[i - 1], nums[i - 2]);
            int right = max(nums[i - 1], nums[i - 2]);
            if (nums[i] > left && nums[i] < right) {
                out_b[0] = left; out_b[1] = right;
                in_b[0] = 0; in_b[1] = 0;
            }
            else {
                if (in_b[0] == 0 && in_b[1] == 0) {
                    in_b[0] = left; in_b[1] = right;
                }
                else {
                    in_b[0] = min(nums[i - 1], in_b[0]);
                    in_b[1] = max(nums[i - 1], in_b[1]);
                }
            }
        }
        flag_before = flag;
    }
    return false;
}
    
int main()
{
    int T, n;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        int* nums = new int[n];
        for (int j = 0; j < n; j++)
            scanf("%d", &nums[j]);
        if (func(n, nums))
            printf("y\n");
        else
            printf("n\n");
        delete[] nums;
    }
    return 0;
}

C++14 解法, 执行用时: 4ms, 内存消耗: 628KB, 提交时间: 2020-05-19 

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
    
using namespace std;
    
bool func(int n, int* nums)
{
    int i, j;
    int out_b[2] = { -2000000, 2000000 };
    int in_b[2] = { 0 };
    int flag, flag_before;
    for (i = 1; i < n; i++) {
        flag = nums[i] < nums[i - 1];
        if (i == 1) {
            flag_before = flag;
            continue;
        }
    
        if (flag == flag_before) {
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            if (in_b[0] == 0 && in_b[1] == 0) {
                in_b[0] = min(nums[i-2], nums[i - 1]);
                in_b[1] = max(nums[i-2], nums[i - 1]);
            }
            else {
                in_b[0] = min(nums[i - 1], in_b[0]);
                in_b[1] = max(nums[i - 1], in_b[1]);
            }
        }
        else if (flag != flag_before) {
            if (nums[i] > in_b[0] && nums[i] < in_b[1])
                return true;
            if (nums[i] < out_b[0] || nums[i] > out_b[1])
                return true;
            int left = min(nums[i - 1], nums[i - 2]);
            int right = max(nums[i - 1], nums[i - 2]);
            if (nums[i] > left && nums[i] < right) {
                out_b[0] = left; out_b[1] = right;
                in_b[0] = 0; in_b[1] = 0;
            }
            else {
                if (in_b[0] == 0 && in_b[1] == 0) {
                    in_b[0] = left; in_b[1] = right;
                }
                else {
                    in_b[0] = min(nums[i - 1], in_b[0]);
                    in_b[1] = max(nums[i - 1], in_b[1]);
                }
            }
        }
        flag_before = flag;
    }
    return false;
}
    
int main()
{
    int T, n;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        int* nums = new int[n];
        for (int j = 0; j < n; j++)
            scanf("%d", &nums[j]);
        if (func(n, nums))
            printf("y\n");
        else
            printf("n\n");
        delete[] nums;
    }
    return 0;
}

上一题

© 2024 nowcoder.com