搜狗编程题
发布于 2017-09-28 23:27 2638 次浏览 2 赞 来自 笔试面试  

数据量最大的30W,所以只能用O(n)的算法。每次只能枚举一个点,然后我们观察到,在圆上,点A,和A点所处直径对应的点B和原上任意的点C,这三个点形成的三角形是一个直角三角形(初中学过的)。A,B可以把圆分为两个半圆,我们如果找到其中一个半圆夹杂的任意两个点D,E,那么A,D,E形成的三角形一定是钝角,因为对应的弧长是大于圆周的一半的。可以在图上画画试试。所以最后的AC代码为:

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 300007;

double angle[maxn];
int n;
const double eps = 1e-10;

int bi_search(double x) {
    int low = 1;
    int high = n;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (angle[mid] > x) {
            high = mid - 1;
        }
        else if (fabs(angle[mid] - x) < eps) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return high;
}
long long getAns(int cnt_a) {
    double p1 = angle[cnt_a];
    double p2 = p1 + 180.0;
    long long result = 0;
    if (fabs(p2 - 360) <= eps) {
        long long cnt_num = n - cnt_a;
        result += (cnt_num * (cnt_num - 1) / 2);
        cnt_num = cnt_a - 1;
        if (fabs(angle[0]) <= eps) {
            cnt_num--;
        }
        result += (cnt_num * (cnt_num - 1) / 2);
    }
    else if (p2 < 360) {
        int loc = bi_search(p2);
        long long cnt_num = loc - cnt_a;
        result += (cnt_num * (cnt_num - 1) / 2);
        cnt_num = n - loc;
        if (fabs(angle[loc + 1] - p2) <= eps) {
            cnt_num--;
        }
        cnt_num += cnt_a - 1;
        result += (cnt_num * (cnt_num - 1) / 2);
    }
    else {
        p2 -= 360;
        int loc = bi_search(p2);
        long long cnt_num = n - cnt_a + loc;
        result += (cnt_num * (cnt_num - 1) / 2);
        cnt_num = cnt_a - loc - 1;
        if (fabs(angle[loc + 1] - p2) <= eps) {
            cnt_num--;
        }
        result += (cnt_num * (cnt_num - 1) / 2);
    }
    return result;
}

int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &angle[i]);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        long long cnt_ans = getAns(i);
        ans += cnt_ans;
    }
    cout << ans / 2 << endl;
}


2 条回复

赞!~

2017-09-29 09:54

大佬是考搜狗北京吧?  面试过了吗?求update

2017-10-19 18:24
添加回复
回到顶部