「题解」多段线(polyline)

多段线(polyline)

【题目描述】

【输入格式】

从文件polyline . in中读入数据。
输入第一行包含一个正整数 ,表示函数个数。
接下来n 行 , 每行包含两个正整数ki , bi,表示第i个函数的参数。

【输出格式】

输出到文件portal . out中。
输出一行一个正整数,表示形成的多段线的图像中不等于180度角的个数

【样例 输入】

1
1
1 0

【样例 输出】

1
1

【样例 输入】

3
-2 -4
1 7
-5 1

【样例 输出】

3

【提示】

函数相关参见高中数学必修 。(看了也没用)
请认真阅读【数据规模及约定】。

【数据规模及约定】

保证对于所有数据有:

本题评测时将开启 O2 优化。

注意，本题中函数<=180度的角就是函数的拐点，也就是说，就是让你求函数的拐点

那么，我们来研究下样例：

对于样例一就很明显了，我们就研究下最后一个样例

我们看下图像：

现在，我们计算一下s(x)的值

这就是s(x)的值．明显的，这个函数有3个拐点（一个在x=7的地方，不容易看出来）

我们就来研究一下这几个函数的关系：

上图就显示了所有函数．

我们可以计算这些函数的零点（与x轴交点）来判断有多少个拐点

各个分函数不同的零点数就是总函数的拐点数

思路明白了，代码就好写了

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

typedef long double lb;

const int MAXN = 100000 + 5;

// 文件锁
#define LOCK

int number, cnt=0;
std::vector<int> Data_k;
std::vector<int> Data_b;
lb withx[MAXN];

void init(){
    scanf("%d", &number);
    for(int i = 1; i <= number; i++){
        int ki, bi;
        scanf("%d %d", &ki, &bi);
        if(ki != 0){
            cnt++;
            Data_k.push_back(ki); Data_b.push_back(bi);
            //求出与函数零点
            withx[cnt] = -(lb)Data_b[cnt] / (lb)Data_k[cnt];
        }
    }
}

int main(int argc, char const *argv[]) {
    // 文件
#ifdef LOCK
    freopen ("polyline.in" , "r", stdin );
    freopen ("polyline.out", "w", stdout);
#endif

    init();

    //去重
    std::sort(withx + 1,withx + 1 + number);
    int Answer = cnt;
    for(int i = 1; i <= cnt; i++)
        if(withx[i] - withx[i - 1] <= 1e-18) Answer--;

    printf("%d", Answer);
    return 0;
}
// Wonderful end

最后给下函数解析式